寻找链表的中间节点

题目描述

给定一个单链表 L，请编写程序输出 L中间结点保存的数据。如果有两个中间结点，则输出第二个中间结点保存的数据。 例如: 给定 L 为 1 -> 7 -> 5，则输出应该为 7; 给定 L 为 1 -> 2 -> 3 -> 4，则输出应该为 3

输入描述

每个输入包含 1 个测试用例。

每个测试用例第 1行给出链表首结点的地址、结点总个数正整数 N(<=10^5)。结点的地址是 5位非负整数， NULL 地址用-1表示 。 接下来有 N 行，每行格式为: Address Data Next 其中 Address 是结点地址，Data 是该结点保存的整数数据(0<=Data<=10^8)，Next是下一结点的地址。

输出描述

对每个测试用例，在一行中输出 L中间结点保存的数据。如果有两个中间结点，则输出第二个中间结点保存的数。

补充说明: 已确保输入的结点所构成的链表L不会成环，但会存在部分输入结点不属于链表L情况

示例1

输入：
00100 4
00000 4 -1
00100 1 12309
33218 3 00000
12309 2 33218

输出：
3

示例2

输入：
10000 3
76892 7 12309
12309 5 -1
10000 1 76892

输出：
7

示例3

输入：
00010 4
00000 3 -1
00010 5 12309
11451 6 00000
12309 7 11451

输出：
6

C++

#include <bits/stdc++.h>

using namespace std;

typedef struct Node {
    int data{};
    string next;
};

int main() {
    string head;
    int n;
    cin >> head >> n;
    unordered_map<string, Node> tab;
    
    // 读取所有节点
    for (int i = 0; i < n; i++) {
        string addr;
        Node node;
        cin >> addr >> node.data >> node.next;
        tab[addr] = node;
    }

    Node node = tab[head];
    // 统计链表L中节点个数
    int linkSize = 1;
    while (tab.find(node.next) != tab.end()) {
        linkSize++;
        node = tab[node.next];
    }

    // 寻找中间节点：跳过一半长度后的节点
    int half = linkSize / 2;
    node = tab[head];
    while (half--) node = tab[node.next];

    cout << node.data << endl;

    return 0;
}

解题思路

这个问题的核心是通过给定的链表节点信息，找出链表的中间节点。具体的要求是：

• 如果链表长度为奇数，输出中间节点的数据。
• 如果链表长度为偶数，输出第二个中间节点的数据。

方法

1. 数据结构选择：使用 unordered_map 来存储链表的节点，键为节点地址，值为节点的内容（数据和下一个节点地址）。
2. 链表遍历：根据给定的首节点地址开始遍历整个链表，统计链表的长度。
3. 找到中间节点：
   • 统计了链表长度后跳过一半节点后指向的即为中间节点。

其他解法：

• 快慢指针[有兴趣的同学自行尝试]

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏