0876：链表的中间结点（1231 分）

力扣第 95 场周赛第 1 题

题目

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

分析

#1

最简单的就是先遍历得到链表长度 n，然后从序号 n//2 的节点即为所求。

1
2
3
4
5
6
7
8

def middleNode(self, head: ListNode) -> ListNode:
	n, p = 0, head
	while p:
		p = p.next
		n += 1
	for _ in range(n//2):
		head = head.next
	return head

40 ms

#2

还有个巧妙的想法，可以用两个指针同时从 head 出发，每轮一个指针移动两步，另一个指针移动一步。 当快指针越界时，慢指针即为所求。

这就是链表中经典的快慢指针法。

解答

1
2
3
4
5

def middleNode(self, head: ListNode) -> ListNode:
	slow = fast = head
	while fast and fast.next:
		slow, fast = slow.next, fast.next.next
	return slow

36 ms