LeetCode 876. Middle of the Linked List

题目:

LeetCode 876. Middle of the Linked List

思路:

刷到这个题的时候, 因为之前做过快慢指针判断链表中是否存在环的问题.

最先想到的解法就是:
因为快指针的速度是慢指针的一倍, 所以当快指针走到尾结点的时候, 慢指针恰好走到中间.

需要注意的就是中间结点的判断: 1. 假如fast.next == null, 代表链表结点的个数是偶数, 此时slow处在中间位置偏左, 因为题目要求取偏右的, 所以返回slow.next
eg: [1, 2, 3, 4, 5, 6], 最终fast = 6,而slow = 3, 故需要返回slow.next即4
2. 假如fast.next != null && fast.next.next == null, 代表链表结点数为奇数, 此时fast是尾结点的前驱结点, slow是中间结点的前驱结点, 故返回slow.next

代码实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (true) {
            if (fast.next == null || fast.next.next == null) {
                return slow.next;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        
    }
}