LeetCode 鏈表分區：按目標值重組鏈表結構

題目描述

給定一個單鏈表的頭節點 head 和一個目標值 x，請將鏈表重新排列，使所有值小於 x 的節點出現在值大於或等於 x 的節點之前。要求保持兩部分節點在原鏈表中的相對順序不變。

範例：

輸入: head = 1→4→3→2→5→2, x = 3
輸出: 1→2→2→4→3→5

解題思路：雙虛擬頭節點法

這是一道典型的鏈表重組問題。我們可以將鏈表視為一串珠子，需要將「紅珠」（小於 x）和「藍珠」（大於等於 x）分別串成兩條線，最後再連接起來。

1. 建立兩個虛擬頭節點 small_dummy 和 large_dummy，分別作為小於 x 和大於等於 x 兩條鏈表的起點
2. 維護兩個尾指針 small_prev 和 large_prev，遍歷原鏈表，將節點依次接到對應鏈表尾部
3. 遍歷結束後，將 large_prev.next 置為 None（斷開可能的循環），然後連接 small_prev.next = large_dummy.next
4. 返回 small_dummy.next 作為新鏈表頭

時間複雜度：O(n)，空間複雜度：O(1)。

Python 參考實現

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    
    def to_list(self):
        return [self.val] + self.next.to_list() if self.next else [self.val]

class Solution:
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        
        small_dummy = ListNode(-1)
        large_dummy = ListNode(-1)
        small_prev = small_dummy
        large_prev = large_dummy
        
        prev = dummy
        while prev.next:
            curr = prev.next
            if curr.val < x:
                small_prev.next = curr
                small_prev = small_prev.next
            else:
                large_prev.next = curr
                large_prev = large_prev.next
            prev = prev.next
        
        # 重要：斷開 large 鏈表尾部，避免循環
        large_prev.next = None
        small_prev.next = large_dummy.next
        
        return small_dummy.next

# 測試
if __name__ == "__main__":
    n1 = ListNode(1)
    n2 = ListNode(4)
    n3 = ListNode(3)
    n4 = ListNode(2)
    n5 = ListNode(5)
    n6 = ListNode(2)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5
    n5.next = n6
    
    r = Solution().partition(n1, 3)
    assert r.to_list() == [1, 2, 2, 4, 3, 5]
    print("測試通過：", r.to_list())

核心要點總結

• 虛擬頭節點：簡化鏈表頭部操作，統一處理邊界情況
• 保持相對順序：遍歷順序即為結果順序，天然滿足穩定性要求
• 斷開尾部：large_prev.next = None 是防止循環引用的關鍵步驟

這道題展示了鏈表分區的標準解法，掌握「雙指針建表 + 尾部連接」的模式，可應用於許多鏈表重組問題。