# 資訊

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

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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

> $L_0 → L_1 → … → L_{n-1} → L_n$

Reorder the list to be on the following form:

> $L_0 → L_n → L_1 → L_{n-1} → L_2 → L_{n-2} → …$

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

> Example 1:
:::success
- Input: head = [1,2,3,4]
- Output: [1,4,2,3]
:::

> Example 2:
:::success
- Input: head = [1,2,3,4,5]
- Output: [1,5,2,4,3]
:::

> Constraints:
:::success
- The number of nodes in the list is in the range $[1, 5 * 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)$