# 148. Sort List
###### tags: `mergesort` `Linked List` `排序` `遞迴`

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

# 思路

1. 再次驗證，medium就是幾個easy 的概念結合起來。
2. 這題就是四個概念
1. merge sort 的基本概念
2. 弟回概念
3. 快慢指針法(實作原本的陣列分割找list中點)
4. 兩個linkedlist 合併
4. 因為跟array left=[:mid] right=[mid:] 不太一樣的邊界值問題，中點在list 屬於left 部分的。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        if not head or not head.next:
            return head

        # 在進行split時，要保留的左邊子list的頭
        left = head

        # divide()函數，回傳右邊子list頭的再前一個node
        # 因為跟array left=[:mid] right=[mid:] 不太一樣的邊界值問題，中點在list 屬於left 部分的。 
        right = self.divide(head)
        tmp = right.next
        right.next = None
        right = tmp

        # recursively split the linked list
        left = self.sortList(left)
        right = self.sortList(right)

        return self.merge(left, right)

    def divide(self, head):
        slow, fast = head, head.next

        while fast and fast.next:
            fast = fast.next.next  # 快指針，每次都以二倍速走
            slow = slow.next
        return slow

    def merge(self, list1, list2):
        cur = ListNode(-1)  # fake node

        # 保留這個linked list進入的端口
        head = cur

        while list1 and list2:
            if list1.val <= list2.val:
                cur.next = list1
                list1 = list1.next # update 它的指針
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next

        if list1:
            cur.next = list1
        if list2:
            cur.next = list2

        return head.next

## 我的解法：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        if not head or not head.next:#遞迴最底
            return head 
        
        left=head 
        
        right=self.divide(head)  # 每一次遞迴後，分成兩半後再次呼叫。
        tem=right.next 
        right.next=None 
        right=tem
        
        
        #每次呼叫，都會在這執行遞迴，直到弟回最底也就是第９行執行
        left=self.sortList(left) 
        right=self.sortList(right)
        
         # 到底(9行)往上回傳return 同時執行merge
        return self.merge(left,right)
    

    def divide(self, head):
        slow=head 
        fast=head.next 
        while fast and fast.next : 
            slow=slow.next 
            fast=fast.next.next 

        return slow 
            
    def merge(self, left,right):

        cur=ListNode(-1) # 建立一個空的linked list 去接串列
        head=cur 
        while left and right: 
            if left.val<right.val :
                cur.next=left 
                left=left.next
            else:
                cur.next=right
                right=right.next 
            cur=cur.next 

        if left:
            cur.next=left 
        else :
            cur.next=right 
        return head.next #因為fakeNode 下一個node 才是valid 值

                    
                
        

c++ 解法