目录

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