資訊

• Question: 143. Reorder List
• From: Leetcode Daily Challenge 2024.03.23
• Difficulty: M1edium

---

目錄

• 資訊
• 目錄
• 題目
• 解法
  • 概念
  • 程式碼
• 複雜度
  • 時間複雜度
  • 空間複雜度

---

題目

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

$L_0\to L_1\to \dots \to L_{n-1}\to L_n$

Reorder the list to be on the following form:

$L_0\to L_n\to L_1\to L_{n-1}\to L_2\to L_{n-2}\to \dots$

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

• Input: head = [1,2,3,4]
• Output: [1,4,2,3]

Example 2:

• Input: head = [1,2,3,4,5]
• Output: [1,5,2,4,3]

Constraints:

• The number of nodes in the list is in the range
  $[1,5\ast {10}^4]$.
• 1 <= Node.val <= 1000

---

解法

概念

這題一樣是先用 two pointers 找到 middle node，然後紀錄 middle node 以後的 nodes，全部丟到 stack 裡面，之後一個一個 pop 出來 append 回 list 就會是 reorder 的順序了

所以程式碼第 11 到 16 行在找 middle node，第 18 到 24 行在把後半部的 nodes 丟到 stack 裡面，而有個小細節是在 stack 裡面的 nodes next 都會是空的，這是因為等等處理 next 的問題比較簡單，畢竟在 stack 裡面的 nodes 都要連回前半部的 nodes，這件事情我在後面一定會做，所以希望這邊不要亂只到我不想要的地方

reorder 的部分也很容易，每一輪都去 stack pop 一個 element 回來連上去就好，這就是程式碼第 26 到 34 行在做的事情

第 35 到 36 行是這次的重點，會因為 list 長度奇偶影響這一部執行與否，但結果都是我要讓最後一個 element 的 next 是 None，這樣 list 才不會變成 cycle，也才是正確的 list

程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # Get the middle of list ( -> slow )
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        # Push last half into stack
        stack = []
        while slow:
            tmp = slow.next
            slow.next = None
            stack.append(slow)
            slow = tmp

        # Reorder the list
        slow = head # Since there is no use in slow, I'll use slow as a pointer instead of renew another pointer
        bk = head
        while stack:
            bk = slow.next
            slow.next = stack.pop()
            slow = slow.next
            slow.next = bk
            slow = slow.next
        if slow:
            slow.next = None

---

複雜度

時間複雜度

使用 two pointers 找到 middle nodes 花了

$O(n)$，push 到 stack 花了

$O(\frac{n}{2})$，最後 reorder 花了

$O(n)$，整體是

$O(n)$

空間複雜度

空間部分因為沒有額外花的記憶體，只有一些小參數而已，所以會是

$O(1)$