86. Partition List
題意
要求將一個鏈結串列重新排列:
- 使所有小於特定值
x
的節點都出現在大於或等於x
的節點之前。 - 分區操作應保持兩個分段中每個節點原始的相對位置(即保持原始順序)。
限制
- 鏈結串列中的節點數量在範圍
[0, 200]
內。 -100 <= Node.val <= 100
-200 <= x <= 200
解題思路
為了解決這個問題,我們可以:
- 創建兩個虛擬節點(dummy nodes),分別代表:
- 所有小於
x
的節點的鏈結串列。 - 所有大於或等於
x
的節點的鏈結串列。
- 所有小於
- 遍歷原始鏈結串列,根據節點的值將它們分配到上述兩個新的鏈結串列中。
- 連接兩個鏈結串列,使小於
x
的節點位於前面,大於或等於x
的節點位於後面。 - 注意:為了避免形成環狀鏈結串列,我們需要將大於或等於
x
的鏈結串列的末尾節點的next
指標設為nullptr
。
程式碼
/**
* 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* partition(ListNode* head, int x) {
// 創建兩個虛擬節點,一個用於存放小於 x 的節點,另一個用於存放大於等於 x 的節點
auto lowerDummy = new ListNode();
auto lower = lowerDummy;
auto greaterDummy = new ListNode();
auto greater = greaterDummy;
// 遍歷鏈表,根據節點值分配到兩個新鏈表
while (head) {
if (head->val < x) {
lower->next = head;
lower = lower->next;
} else {
greater->next = head;
greater = greater->next;
}
head = head->next;
}
// 斷開大於等於 x 的鏈表的末尾,避免循環引用
greater->next = nullptr;
// 連接兩個鏈表
lower->next = greaterDummy->next;
// 返回重新排列後的鏈表頭節點
return lowerDummy->next;
}
};
時間與空間複雜度分析
- 時間複雜度:O(N),其中 N 是鏈結串列的節點數量。
- 分析:我們只需要遍歷一次原始鏈結串列,每個節點只被訪問一次,因此時間複雜度為線性。
- 空間複雜度:O(1)。
- 分析:我們使用了固定數量的額外指標(如
lowerDummy
、lower
、greaterDummy
、greater
),沒有使用與輸入大小相關的額外空間,因此空間複雜度為常數級別。
- 分析:我們使用了固定數量的額外指標(如
Comments ()