###### tags: `Leetcode` `medium` `list` `pointer` `python`

# 143. Reorder List

## [題目連結:] https://leetcode.com/problems/reorder-list

## 題目
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.


**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]

#### [圖片來源]: https://leetcode.com/problems/reorder-list/

## 解題想法:
* 此題目為，希望重連node，頭->尾->頭->尾.....
* 想法: 使用pointer
* slow、fast
* step1:分成兩段
* 若node總數奇數
* 第一段多，第二段少
* step2:斷乾淨後
* **反轉第二段**
* step3: 兩段再交叉插入相連
* 分別先記錄下一組:head1.next、head2.next
* 連當前的head1、head2


## Python:

#用slow fast pointer:分兩段 本題: 若遇奇數 第一段多 第二段少
#與P148.py相同概念但不同分法
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head = self
        res = []
        while head:
            res.append(head.val)
            head=head.next
        print(res)

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        slow=head
        fast=head
        #先找最中間點
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        second=slow.next
        #斷乾淨
        slow.next=None
        #reverse second list
        pre=None
        cur=None
        while second:
            cur=second.next
            second.next=pre
            pre=second
            second=cur
        #combined
        head2=pre
        head1=head
        while head1 and head2:
            #先記錄下一組起始位置
            tmp1=head1.next
            tmp2=head2.next
            #連結
            head1.next=head2
            head2.next=tmp1
            #移到下一組
            head1=tmp1
            head2=tmp2
            
root = ListNode(1)
root.insert(2)
root.insert(3)
root.insert(4)
root.insert(5)
root.insert(6)
print("Old  :",end='')
root.printList() #Old  :[1, 2, 3, 4, 5, 6]

result=Solution()
ans=result.reorderList(root)
print("Atfer:",end='')
root.printList() #Atfer:[1, 6, 2, 5, 3, 4]