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 之间。

题解

两个思路：

1. 遍历链表得到链表长度，然后找到 $\frac{length}{2}$ 处节点
2. 如果想一次遍历就得到中间节点，可以使用 快慢指针 技巧，我们让两个指针 slow 和 fast 分别指向头节点 head，每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

代码实现

// 思路一
func middleNode1(head *ListNode) *ListNode {
	slow, fast := head, head

	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next // 假设链表长度为 k，当 fast 走到末尾时，slow 走到 k/2
		slow = slow.Next
	}
	return slow
}

// 思路二
func middleNode(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	l1 := head
	length := 0
	for l1 != nil {
		length++
		l1 = l1.Next
	}
	k := length / 2
	l1 = head
	for k > 0 {
		l1 = l1.Next
		k--
	}
	return l1
}