876.链表的中间节点

问题描述

给你单链表的头结点 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

解法一：快慢指针

下面的 for 循环结束后，fast == nil 或 fast.Next == nil，即 fast 指向空节点或当前链表的最后一个节点。由于 fast 每次走两步，故最终走的步数是偶数。如果 fast 最后指向的是空节点，则表明链表节点的数目为偶数，此时 slow 指向两个中间节点中靠后的那一个。如果 fast 最后指向链表最后一个节点，则表明此时链表的数目为奇数，此时 slow 指向唯一的中间节点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

拓展

当链表节点数目为偶数时，如何获取两个中间节点中靠前的那一个?

先处理 head == nil 的特殊情况，后将 for 循环的进入条件由 fast != nil && fast.Next != nil 改为 fast.Next != nil && fast.Next.Next != nil 即可。代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}