【LeetCode】143. Reorder List 解題報告

143. Reorder List / Medium

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

  • The number of nodes in the list is in the range [1, 5 * 10^4].
  • 1 <= Node.val <= 1000

思路

這一題乍看複雜,其實不然。實際上可以被分成三個步驟:找中點、翻轉、合併。
由於題目要求要在原來的 List 上進行操作,我們不能存到另一個新的 List。
首先找到整個 List 的中點,將 List 從中點斷開,形成兩個獨立的 List。
接著翻轉(Reverse)後半部的 List,最後再將後半部 List 的節點間隔地插入到前半部 List。

前兩個步驟可以參考另外兩題:

    1. Middle of the Linked List
    1. Reverse Linked List

尋找中點

使用快慢指標,快的指標走兩步,慢的走一步,當快指標到 List 的尾巴時,慢的會剛好在中間。

翻轉 / 合併 List

好像沒什麼特別的,畫個圖就能理解了。很簡單的指標操作。

效能

Complexity

  • Time Complexity: O(N)
  • Space Complexity: O(1)

LeetCode Result

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
void reorderList(ListNode* head) {
if(!head || !head->next || !head->next->next) return;

// 1. Find the Middle Node
ListNode *fast = head, *slow = head;
while(fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}

// 2. Reverse the Second List
ListNode *cur = slow->next, *pre = NULL;
slow->next = NULL;
while (cur != nullptr) {
ListNode *next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}

// 3. Merge Two Lists
ListNode *t1, *t2;
while(head != nullptr && pre != nullptr) {
t1 = head->next;
t2 = pre->next;
head->next = pre;
pre->next = t1;
head = t1;
pre = t2;
}

}
};