跳至主要内容

86. Partition List

86. Partition List

題意

  • 要求將一個 linked list 重新排序

    • 使所有小於特定值 x 的節點都出現在大於或等於 x 的節點之前

    • 分區操作應保持兩個分段中每個節點原始的相對位置

限制

  • The number of nodes in the list is in the range [0, 200].

  • -100 <= Node.val <= 100

  • -200 <= x <= 200

思考

  • 解決這個問題的一個直觀方法是創建兩個臨時的虛擬節點,分別表示所有小於 x 的節點和所有大於或等於 x 的節點

  • 遍歷原始鏈表,根據節點的值將它們分配到兩個新的鏈表中,最後再將這兩個鏈表連接起來

/**
* 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;
}
};