Blog

題目

Given the head of a singly linked list, return the middle node of the linked list.

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

意思是給你一個single list的頭節點 head，返回list的中間節點。

如果list的長度為偶數，則有兩個中間節點，請返回第二個中間節點。

思路

我們可以用快慢指針來處理，讓 first 跟 slow 一開始都指向 head(index 為0的位置)。

每次slow都往前一步，first都往前兩步，這樣子當first走完時，slow就會剛好在中間的位置。

考慮到head為null或是只有一個節點(head)的情況

就直接返回head了。

考慮偶數節點的情況

第1次執行完時

first 前進到 index為 2 的位置
slow 前進到 index為 1 的位置

第2次執行完時

first 前進到 index為 4 的位置
slow 前進到 index為 2 的位置

第3次執行時

first 前進到 null
slow 前進到 index為 3 的位置

考慮奇數節點的情況

第1次執行完時

first 前進到 index為 2 的位置
slow 前進到 index為 1 的位置

第2次執行完時

first 前進到 index為 4 的位置
slow 前進到 index為 2 的位置

第3次執行時

如果是偶數節點直接用first = first.next.next，不會怎樣
But But But奇數節點有一個小細節，如果直接first = first.next.next，在奇數節點時，會發生什麼事？

會發生exception

所以我們要多加一個判斷，first的下一個位置是否為空，如果是空就return slow了。

解法

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

        ListNode fast = head;
        ListNode slow = head;

        while(fast != null){
            fast = fast.next;

            if(fast == null){
                return slow;
            }
            
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}

Complexity

• Time complexity:O(n)
• Space complexity:O(1)