題目

解題概念

  • 此題簡單來說，就是要切割一 Linked List head，使它所有小於 x 的節點都位於大於等於 x 的節點之前 (節點順序不能改變)
  • 而實際執行上，我用兩個 Linked List before 與 after 去操作 :
    1. 搜尋過 Linked List head 的每個元素 :
      • 若 head.val >= x，則將其放入 after 中
      • 若 head.val < x，則將其放入 before 中
    2. 合併 before 與 after，並回傳

實際寫Code

  • 目標函式 : partition(head, x)
    • Input : head: ListNode、x: int
    • Output : ListNode
  • 前置作業 : 
    1
    2
    3
    4
    before = ListNode()
    b = before # 作為等等迴圈使用之變數
    after = ListNode()
    a = after # 作為等等迴圈使用之變數
  • 主要程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    while head != None :

        # 建立新節點
        new_node = ListNode(val = head.val)
        
        # 判斷新節點要加到 before 或 after
        if head.val >= x :
            a.next = new_node
            # a 指標往後移
            a = a.next
        else:
            b.next = new_node
            # b 指標往後移
            b = b.next
            
        # head 也往後移
        head = head.next

    # 合併 before 和 after
    b.next = after.next

    return before.next