力扣_876. 链表的中间结点

力扣_876. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

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

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

思路是遍历两次链表，第一遍用来统计链表长度size，对长度模运算判断是否为奇偶数后，第二遍遍历链表取中间结点；一开始还对使用了if判断，想着偶数的话节点取size/2+1，奇数节点取size/2，后来发现直接取size/2就行啦。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    
    public ListNode middleNode(ListNode head) {
        int size = 0;
        ListNode current = head;
        while (current != null) {
            size++;
            current = current.next;
        }
        int index = size / 2;
        ListNode cur = head;
        // 获取链表中某个位置的元素
        for (int i = 1; i <= index; i++) {
            cur = cur.next;
        }
        return cur;
    }
}

看了题解后发现还是快慢指针法牛，一开始还不明白为什么当快指针到达链表的末尾时，慢指针正好指向链表的中间节点。ai了一下懂了，假设链表的长度为 n。我们从头开始，快慢指针都指向链表的第一个节点。快指针的移动速度比慢指针快，因此，快指针的每一步移动相当于慢指针的两步。当快指针走到链表的末尾时，它已经走过了大约 n 步。慢指针每次只走一步，所以它的移动速度相对较慢。由于快指针走得更快，当快指针走到链表的末尾时，慢指针实际上已经走过了 n/2 步。在这段过程中，慢指针每次走一步，它会在快指针走 n 步时，正好走过 n/2 步。妙蛙种子！