刷题笔记合集🔗

单向链表中间节点

问题描述

给定一个单向链表，求链表中间节点的值。如果节点数为奇数，取中间节点；如果为偶数，取偏右边的那个节点值。

输入格式

第一行包含两个整数，分别表示链表头节点的地址和后续输入的节点数 。

接下来的 行，每行包含三个部分，格式为：节点地址 节点值 下一个节点地址。其中，节点地址为 5 位数字，节点值为整数，下一个节点地址为 5 位数字或 -1（表示空指针）。

输出格式

输出一个整数，表示单向链表中间节点的值。

样例输入1

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

样例输出1

6

样例输入2

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

样例输出2

7

样例解释

数据范围

• 
• 节点值范围：
• 节点地址为 5 位非负整数

题解

快慢指针

这道题目要求找出单向链表的中间节点。解决这个问题的关键在于如何在只遍历一次链表的情况下找到中间节点。一个巧妙的方法是使用快慢指针。

快慢指针法的核心思想是：

1. 设置两个指针，快指针和慢指针，初始时都指向链表头部。
2. 快指针每次移动两步，慢指针每次移动一步。
3. 当快指针到达链表末尾时，慢指针恰好在中间位置。

为什么这个方法有效？

想象一下，如果快指针的速度是慢指针的两倍，那么当快指针走完全程时，慢指针正好走了一半。这就是这个方法的精妙之处。

具体实现步骤：

1. 首先，需要根据输入构建链表。可以使用哈希表存储节点信息，键为节点地址，值为节点对象（包含值和下一个节点地址）。

2. 从头节点开始，使用快慢指针遍历链表：

   • 慢指针每次移动一步
   • 快指针每次移动两步
   • 如果快指针到达末尾或下一个节点是末尾，结束遍历

3. 遍历结束后，慢指针指向的就是中间节点（偶数个节点时是偏右的中间节点）

4. 返回慢指针指向的节点的值

参考代码

当然，我会为每种语言的代码添加详细的注释。以下是添加了详细注释的五种语言的代码：

• Python

class Node:
    def __init__(self, val, next_addr):
        self.val = val  # 节点的值
        self.next_addr = next_addr  # 下一个节点的地址

def get_result(head, nodes):
    # 初始化慢指针为头节点
    slow = nodes[head]
    # 初始化快指针为慢指针的下一个节点，如果存在的话
    fast = nodes[slow.next_addr] if slow.next_addr != '-1' else None

    # 当快指针不为空时，继续遍历
    while fast is not None:
        # 慢指针移动一步
        slow = nodes[slow.next_addr]
        # 快指针移动一步
        fast = nodes[fast.next_addr] if fast.next_addr != '-1' else None
        if fast is None:
            break
        # 快指针再移动一步
        fast = nodes[fast.next_addr] if fast.next_addr != '-1' else None

    # 返回慢指针所在节点的值，即中间节点的值
    return slow.val

# 输入处理
head, n = input().split()  # 读取头节点地址和节点数量
nodes = {}  # 用字典存储所有节点
for _ in range(int(n)):
    addr, val, next_addr = input().split()  # 读取每个节点的信息
    nodes[addr] = Node(int(val), next_addr)  # 创建节点对象并存储

# 输出结果
print(get_result(head, nodes))  # 调用函数并打印结果

• C

// 待补充

• Javascript

const readline = require('readline');

class Node {
    constructor(val, nextAddr) {
        this.val = val;  // 节点的值
        this.nextAddr = nextAddr;  // 下一个节点的地址
    }
}

function getResult(head, nodes) {
    // 初始化慢指针为头节点
    let slow = nodes.get(head);
    // 初始化快指针为慢指针的下一个节点，如果存在的话
    let fast = slow.nextAddr !== '-1' ? nodes.get(slow.nextAddr) : null;

    while (fast !== null) {
        // 慢指针移动一步
        slow = nodes.get(slow.nextAddr);
        // 快指针移动一步
        fast = fast.nextAddr !== '-1' ? nodes.get(fast.nextAddr) : null;
        if (fast === null) break;
        // 快指针再移动一步
        fast = fast