单向链表中间节点

单向链表中间节点

#链表 2025-03-30

#include <iostream>
#include <utility>
#include <vector>
#include <list>
#include <ostream>
#include <sstream>
#include <unordered_map>

using namespace std;

struct LinkList {
  int val_;
  LinkList *next_;

  explicit LinkList(int val, LinkList *next = nullptr)
	  : val_(val), next_(next) {}
};

LinkList *buildLink(unordered_map<std::string, pair<int, std::string >> &mp, std::string &start) {
	auto len = mp.size();
	LinkList *link = nullptr;
	LinkList *re = nullptr;
	for (int i = 0; i < len; ++i) {
		auto &[val, end] = mp[start];
		start = end;
		auto link_node = new LinkList(val, nullptr);
		if (link == nullptr) {
			link = link_node;
			re = link;	// 记录头节点，后续返回
		} else {
			link->next_ = link_node;	// 更新节点
			link = link->next_;
		}
	}
	return re;
}

int findMiddle(LinkList *head, int len) {
	int middle = len / 2;
	auto tmp = head;
	for (int i = 0; i < middle; ++i) {
		tmp = tmp->next_;
	}
	return tmp->val_;
}

void clear(LinkList *head) {
	while (head != nullptr) {
		auto tmp = head->next_;
		head->next_ = nullptr;
		delete head;
		head = tmp;
	}
}

int main() {
	std::string startAddr;
	int num;

	std::string data;
	getline(cin, data);
	istringstream iss(data);
	iss >> startAddr >> num;

	unordered_map<std::string, pair<int, std::string >> map_;
	for (int i = 0; i < num; ++i) {
		getline(cin, data);
		istringstream iss2(data);
		std::string start, end;
		int val;
		iss2 >> start >> val >> end;
		map_[start] = make_pair(val, end);
	}

	auto link = buildLink(map_, startAddr);

	cout << findMiddle(link, num) << endl;

	clear(link);

	return 0;
}

buildLink 构建链表的时候，记得更新节点信息，同时记录最开始的 头结点信息返回。

程序的最后，还可以把 链表的对内存回收一下，尽管你可以考虑用智能指针，更加优雅。