链表的中间结点

题目 LeetCode # 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，我们返回第二个结点。

题解

使用快慢指针, 快指针步长为 2, 慢指针步长为 1, 当快指针走到末尾时, 慢指针恰好走到中点. 循环的终止条件应为快指针的下个或下下个结点为空.

Java

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class MiddleNode {
    public ListNode middleNode(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode fastPointer = head;
        ListNode slowPointer = head;
		
		/*
        若要获取偶数长度链表中间结点中的前一个则改为:
        while (fastPointer.next != null && fastPointer.next.next != null)
         */
        while (fastPointer != null && fastPointer.next != null) {
            fastPointer = fastPointer.next.next;
            slowPointer = slowPointer.next;
        }

        return slowPointer;
    }
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    return slow