1 題目描述

有一個linked list，要求將linked list中小於x的node放在前面，大於等於x的node放在後面。

2 解法

這題不難，可以直接使用兩個linked list，一個是小於x的linked list，一個是大於等於x的linked list，最後再將兩個linked list合併即可。

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
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        # 建立兩個虛擬頭節點，分別用於小於x的節點和大於等於x的節點
        small_head = ListNode(0)
        large_head = ListNode(0)
        
        # 當前指針指向小鏈表和大鏈表的頭節點
        small = small_head
        large = large_head
        
        # 遍歷原鏈表
        cur = head
        while cur:
            if cur.val < x:
                # 添加節點到小於x的鏈表
                small.next = cur
                small = small.next
            else:
                # 添加節點到大於等於x的鏈表
                large.next = cur
                large = large.next
            cur = cur.next
        
        # 將大鏈表的最後一個節點的 next 設置為 None，避免循環鏈表
        large.next = None
        
        # 將小於x的鏈表的尾部連接到大於等於x的鏈表的頭部
        small.next = large_head.next
        
        return small_head.next

3 總結

一開始我傻傻的，沒有think out of the box，我是遍歷一個個節點，發現要換位置的時候進行處理，沒想到讓整個串接過程變得非常複雜，結果沒想到使用兩個linked-list就可以處理了，但是相對的這個空間複雜度是O(n)，如果題目限制空間複雜度是O(1)的話，那麼這個解法就不適用了。