[LeetCode]876. Middle of the Linked List

Algorithm I 筆記撰寫計畫

敘述

這是 Algorithm I 第五天第一個題目，總共有兩題。

• 難度: Easy
• 花費時間: 30min
• 題目

給你一個 linked list 的 head ，回傳 linked list 正中央的 node ，如果 linked list 是偶數的話，就回傳中間第二個值。

點我開啟限制與範例

限制:

The number of nodes in the list is in the range [1, 100].
1 <= Node.val <= 100

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

筆記

這道題稍微看一下題目就看的出來，是為了 Two Pointer 特別設計的，一個 Pointer 一次走一步，另一個一次兩步，等另一個走到 List 最後，再回傳第一個就好。

作法如下:

• mainPointer: 一次兩步，直到撞到最後
• delayPointer: 一次一步， mainPointer 撞到最後，就回傳值。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
let middleNode = function(head) {
    let mainPointer = head;
    let delayPointer = head;
    while (mainPointer) {
        if (!mainPointer.next) break;
        delayPointer = delayPointer.next;
        if (!mainPointer.next.next) break;
        mainPointer = mainPointer.next.next;
    }
    return delayPointer;
};

成績

點我開啟舊寫法/失敗寫法