876_middle_of_the_linked_list

876. 链表的中间结点 简单

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

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

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

• 给定链表的结点数介于 1 和 100 之间。

代码参考：

package main

import "fmt"

func main() {
    fmt.Println(middleNode(newList([]int{1, 2, 3, 4, 5})))
    fmt.Println(middleNode(newList([]int{1, 2, 3, 4, 5, 6})))
}

// 考虑遍历的两种普遍问题
// 间距问题：使用2个间距指针 front, rear
// 截取1/N问题：使用2个倍速指针 slow, fast
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 移动到中间节点即可
func middleNode1(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    n := 0
    cur := head
    for cur != nil {
        n++
        cur = cur.Next
    }
    mid := n / 2
    for i := 0; i < mid; i++ {
        head = head.Next
    }
    return head
}