题目描述

给定一个单链表 L ，请编写程序输出 L 中间结点保存的数据。

• 如果链表有一个中间结点，输出该结点数据；
• 如果链表有两个中间结点，输出第二个中间结点的数据。

输入格式：

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

1. 第一行给出链表首结点的地址和结点总个数 N （ N <= 10^5 ）。
2. 接下来有 N 行，每行包含三个内容：结点地址、结点数据、下一结点地址。

解题思路

1. 构建链表：首先将所有结点的信息（地址、数据、下一结点地址）存储在一个字典 nodes 中，地址作为键，值为一个包含数据和下一结点地址的元组。
2. 遍历链表：从给定的头结点地址开始遍历链表，同时计数。由于链表中的结点数已知，所以中间结点的位置可以通过总长度计算得出。如果总结点数为奇数，直接定位到中间位置；如果为偶数，定位到第二个中间结点的位置。
3. 输出结果：在遍历到目标位置后，输出该结点的数据。

复杂度分析

• 时间复杂度： O(N) 。遍历链表时访问所有结点。
• 空间复杂度： O(N) 。存储所有结点的地址信息。

代码实现

C++

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
    string head;
    cin >> head;

    int n;
    cin >> n;

    map<string, pair<int, string>> nodes;
    for (int i = 0; i < n; i++) {
        string addr;
        cin >> addr;

        int val;
        cin >> val;

        string nextAddr;
        cin >> nextAddr;

        nodes[addr] = {val, nextAddr};
    }

    string now = head;
    int id = 1;
    while (now != "-1") {
        if (id == (n / 2 + 1)) {
            cout << nodes[now].first << endl;
            break;
        }
        now = nodes[now].second;
        id++;
    }

    return 0;
}

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String head = sc.next();
        int n = sc.nextInt();
        
        Map<String, Node> nodes = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String addr = sc.next();
            int val = sc.nextInt();
            String nextAddr = sc.next();
            nodes.put(addr, new Node(val, nextAddr));
        }
        
        String now = head;
        int id = 1;
        while (!now.equals("-1")) {
            if (id == (n / 2 + 1)) {
                System.out.println(nodes.get(now).data);
                break;
            }
            now = nodes.get(now).next;
            id++;
        }
        
        sc.close();
    }
}

class Node {
    int data;
    String next;

    Node(int data, String next) {
        this.data = data;
        this.next = next;
    }
}

Python

def find_middle_node(head, nodes_info, n):
    nodes = {}
    for addr, val, next_addr in nodes_info:
        nodes[addr] = (val, next_addr)
    
    now = head
    id = 1
    while now != "-1":
        if id == (n // 2 + 1):
            print(nodes[now][0])
            break
        now = nodes[now][1]
        id += 1

# 读取输入
head = input().strip()
n = int(input().strip())
nodes_info = [input().strip().split() for _ in range(n)]
nodes_info = [(addr, int(val), next_addr) for addr, val, next_addr in nodes_info]

find_middle_node(head, nodes_info, n)

题目描述

给定一个单链表 $L$ ，请编写程序输出 $L$ 中间结点保存的数据。

如果有两个中间结点，则输出第二个中间结点保存的数据。例如：

给定 $L$ 为 $1→7→5$，则输出应该为 $7$ ；

给定 $L$ 为 $1→2→3→4$，则输出应该为 $3$ ；

输入描述

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

每个测试用例：

第一行给出链表首结点的地址、结点总个数正整数 $N （≤ 10^5）$。

结点的地址是 $5$ 位非负整数，$NULL$ 地址用 $-1$ 表示。

接下来有 $N$ 行，每行格式为：

$Address Data Next$

其中 $Address$ 是结点地址，$Data$ 是该结点保存的整数数据$（0 ≤ Data ≤ 10^8）$，$Next$ 是下一结点的地址。

输出描述

对每个测试用例，在一行中输出 $L$ 中间结点保存的数据。

如果有两个中间结点，则输出第二个中间结点保存的数据。

备注

已确保输入的结点所构成的链表 $L$ 不会成环，但会存在部分输入结点不属于链表 $L$ 情况 。

样例1

输入

00010 4
00000 3 -1
00010 5 12309
11451 6 00000
12309 7 11451

输出

6

样例2

输入

10000 3
76892 7 12309
12309 5 -1
10000 1 76892

输出

7