143. Reorder List

Problem Description

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Thoughts

1. 題目說要 in-place 修改linked list

   • 可以試著直接修改linked list，做到 O(1) 空間複雜度。

2. 要把順序從 1->2->3->4，變成1->4->2->3，假設資料結構是Array不是linked list，最直觀的想法是建兩個 iterator，一個從頭開始iterate，另一個從尾開始iterate，兩個彼此輪流插入資料。

   • 但今天是 singly linked list，從頭iterate做得到但從尾 iterate 做不到，除非有做一些改變。
   • 在O(1)空間複雜度的限制下，可能的做法是直接修改後半段的Linked list，讓他反過來。
   • E.g.
     • 1->2->3->4 => 1 -> 2, 3 <- 4
     • 1->2->3->4->5 => 1 -> 2 -> 3, 4 <- 5
   • 反過來後，就可以做到上述講的事情。

3. 反過來後要考慮如何切開這兩個linked list會比較好做

   • 假設切完後要開始建linked list，算法可能會長這樣:

   while head and tail:
     tmp1 = head.next
     tmp2 = tail.next
   
     # Start linking
     head.next = tail
     tail.next = tmp1
   
     # To next
     head = tmp1
     tail = tmp2

• 此時要思考前一步驟如何切linked list會讓這個算法比較好處理。
• 同時，也需考慮linked list長度為奇數或偶數的情況下要怎麼處理
  • 分開case處理會比較容易想
• 若要不分開case處理(奇數偶數case一起處理)，有個方法是在找出 mid和mid_next後:
  • 把mid.next, mid_next.next 設為空值
  • 對偶數長度的case來說，這裡的mid為中間靠左邊的點。
  • 像是上述例子的切法就為此種切法。
• 這樣設置後執行上述的演算法便不會有問題了。

Solution

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # first reverse right-half, and iterate and link
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # slow now is in middle
        # From slow, start reverse
        mid = slow.next
        prev = None
        while mid:
            tmp = mid.next
            mid.next = prev
            prev = mid
            mid = tmp
        # Cut off two linkedlist
        slow.next = None
        tail = prev

        ans = head
        # Start re-linking
        while head and tail:
            tmp1 = head.next
            tmp2 = tail.next

            head.next = tail
            tail.next = tmp1
            
            head = tmp1
            tail = tmp2
        return ans