Skip to content

LeetCode: 876-Middle of the Linked List 解題紀錄

Last Updated on 2022-12-05 by Clay

題目

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.

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.

Constraints:

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

    題目非常地單純,就是給定一個儲存整數數列的鏈結串列(linked-list)。我們要做的,就是回傳這個鏈結串列中的『中間數』(middle of the linked list)。

    題目也給定了這個中間數的定義。如果是奇數的數列,則是串列中間的選點;如果是偶數的數列,則是第二個中間節點。

    第二個中間節點是什麼意思呢?假設我們有以下的數列:

    [1, 2, 3, 4, 5, 6]


    中間的節點應該有兩個:3 and 4。而我們要回傳的節點就是第二個,4 的節點。


    解題思路

    Brute Force

    最簡單粗暴的方法,就是先把鏈結串列跑到底,知道了整個鏈結串列的長度後,接著再執行一遍把鏈結串列走到底的步驟,這次在長度的一半就返回節點。


    Brute Force 複雜度

    Time ComplexityO(n)
    Space ComplexityO(1)

    雖然看起來是 O(n),不過實際上會比優化過的方法更慢一些。畢竟實際上,暴力法的解法應該是跑了 1.5n 的時間單位。


    C++ 範例程式碼

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
    public:
        ListNode* middleNode(ListNode* head) {
            ListNode* currNode = head;
            int length = 0;
            
            while (currNode) {
                ++length;
                currNode = currNode->next;
            }
            
            ListNode* returnNode = head;
            for (int i=0; i<length/2; ++i) {
                returnNode = returnNode->next;
            }
            
            return returnNode;
        }
    };



    Python 範例程式碼

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
            curr = head
            length = 0
            
            while curr:
                length += 1
                curr = curr.next
            
            result = head
            for i in range(length//2):
                result = result.next
    
            return result



    兩節點走訪

    另外一個方法就是建立兩個走訪速度不一樣的節點。第一個節點每次指往前走一步、第二個節點則是每次往前走兩步。

    由於第二個節點的走訪速度是第一個節點的兩倍,所以當第二個節點走到底時,第一個節點會剛好走到一半。


    兩節點走訪 複雜度

    Time ComplexityO(n)
    Space ComplexityO(1)


    C++ 範例程式碼

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
    public:
        ListNode* middleNode(ListNode* head) {
            ListNode* slow = head;
            ListNode* fast = head;
    
            while (fast && fast->next) {
                slow = slow->next;
                fast = fast->next->next;
            }
            
            return slow;
        }
    };



    Python 範例程式碼

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
            slow = head
            fast = head
    
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            
            return slow
    

    References


    Read More

    Leave a Reply取消回覆

    Exit mobile version