# 143. Reorder List

https://leetcode.com/problems/reorder-list/

## 思路：
1. 先去把linked list 分兩段->快慢指針
2. 再去reverse list
3. 在合併linkedl list
4.

## 特別要說的是合併的程式碼

       first, second = head, head_of_second_rev
        
        while second.next:
            
            tem=first.next # 暫存
            first.next = second # 連接第二linkes list 
            first = tem # 把暫存在存回來first 當作第一個linkes list 的首節點。方便下次運算。
            
            tem = second. # 暫存
            second.next = first # 第二個節點前一個已經被first 接上了，再來第二個節點接上下一個(已經換成原本first 的下一個的first 節點(就是原本first 的第二個節點))
            second = tem # # 把暫存在存回來first 當作第一個linkes list 的首節點。方便下次運算。

next_hop 先存了first的next 節點，因為我們等等會把first.next 接到翻轉後的第二個linkedlist ，所以和原先first 的next 鏈結會斷掉，所以先暫存
所以也可以寫成`tem=first.next` 比較好理解

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        
        if not head:
            # Quick response for empty linked list
            return None
        
        # ------------------------------------------
        # Locate the mid point of linked list
        # First half is the linked list before mid point
        # Second half is the linked list after mid point
        
        fast, slow = head, head
        
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            
        mid = slow
        
        # ------------------------------------------
        # Reverse second half
        
        prev, cur = None, mid
        
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        
        head_of_second_rev = prev
        
        # ------------------------------------------
        # Update link between first half and reversed second half
        
        first, second = head, head_of_second_rev
        
        while second.next:
            
            next_hop = first.next
            first.next = second
            first = next_hop
            
            next_hop = second.next
            second.next = first
            second = next_hop