刷题笔记合集🔗

单向链表中间节点

问题描述

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

输入格式

第一行包含链表头节点地址和后续输入的节点数 。

后续输入每行表示一个节点，格式为节点地址、节点值、下一个节点地址（ 表示空指针）。

输入保证链表不会出现环，并且可能存在一些节点不属于链表。

输出格式

输出单向链表中间的节点值。

样例输入

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

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

样例输出

6

7

数据范围

题解

这道题要我们找出单向链表的中间节点。对于奇数个节点的链表，中间节点就是正中间那个；对于偶数个节点的链表，中间节点取偏右边的那个。

解决这个问题有两种常见方法：

方法一：遍历两次链表

1. 第一次遍历链表，统计链表的长度
2. 计算中间节点的位置
3. 第二次遍历链表，找到中间节点

这种方法简单直观，但需要遍历链表两次。

方法二：快慢指针（更优）

快慢指针是解决链表中间节点问题的经典方法：

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

这种方法只需要遍历一次链表，效率更高。

本题的特殊之处在于输入格式不是直接给出链表，而是以节点地址、值和下一节点地址的形式给出，我们首先需要构建链表。另外，输入中可能包含不属于链表的节点，需要从头节点开始遍历，才能确定真正的链表结构。

时间复杂度：O(n)，其中n是链表的长度，我们只需遍历链表一次。 空间复杂度：O(n)，需要存储所有节点的信息。

对于本题给定的数据范围来说，这个时间和空间复杂度是完全可接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
head_addr, n = input().split()
n = int(n)

# 存储所有节点信息
nodes = {}
for _ in range(n):
    addr, val, next_addr = input().split()
    nodes[addr] = (val, next_addr)

# 找出链表中间节点
def find_middle(head_addr, nodes):
    # 使用快慢指针找中间节点
    slow = head_addr
    # 如果存在下一个节点，fast指向下一个节点
    fast = nodes[slow][1] if nodes[slow][1] != '-1' else None
    
    # 当fast能移动时继续遍历
    while fast and fast != '-1':
        # slow移动一步
        slow = nodes[slow][1]
        # fast移动一步
        fast = nodes[fast][1]
        # 如果fast能再移动一步，继续移动
        if fast and fast != '-1':
            fast = nodes[fast][1]