876-链表的中间节点

LeetCode 876. Middle of the Linked List

LeetCode-876

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])

method: 双指针

两个指针一开始都指向头结点，快指针每次走两步，慢指针每次走一步
用快指针作为判断条件，fast指针为空，或者下一个节点为空就退出

ListNode* middleNode(ListNode* head) {
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}