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 Complexity | O(n) |
| Space Complexity | O(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 Complexity | O(n) |
| Space Complexity | O(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