###### tags: `Leetcode` `medium` `list` `sort` `divide and conquer` `python` `c++` `Top 100 Liked Questions`

# 148. Sort List

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

## 題目:

Given the ```head``` of a linked list, return the list after sorting it in **ascending order**.

**Follow up**: Can you sort the linked list in **O(n logn) time** and **O(1) memory** (i.e. constant space)?


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

## 解題想法:
* 題目為要求排序list
* time: 要求O(n logn)
* space: 要求O(1)

* 使用merge sort
* (法1) topDowm:
* 使用快慢pointer: 分兩段彼此再遞迴，最後再merge
* time: O(NlongN)
* space: O(n)
* (法2)buttonUp:
* 將元素兩兩merge，再兩兩merge....
* time: O(NlongN)
* space: O(n)
* 但有網路大神說可以到O(1)???
* 小的不才 不懂為啥不是O(N)是O(1)...
* 思考:
* 網路上標準解答都是用Top-down方法:
* 且此題的歸類有 **divide and conquer**
* 但這題要求O(1)的空間??
* 實際上應該**最多為O(n)而已**
* 原因:
* 添加新list Node數量會隨著遞歸次數增加，不是常數量
* 遞歸本身就不是常數空間

## Python:
* 可參考 [143. Reorder List](/YkakbugKSpyg0u8KQ-g2eQ) 作法
* 使用slow fast pointer:
* 分兩段: 若遇**奇數**
* **第一段少**
* 第二段多
* 因為此題若讓第一段多，run and submit時會報錯誤(runtimeerror: maximum recursion depth exceeded)
* P143為: 若遇奇數 第一段多 第二段少

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
        stack=[]
        while head:
            stack.append(head.val)
            head=head.next
        print(stack)

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        #使用merge sort:
        #法1: topDowm: 使用快慢pointer: 分兩段彼此再遞迴，最後再merge
        #   time: O(NlongN) space: O(n)
        if not head or not head.next:
            return head
        fast=head
        slow=head
        tail=None #first part's end
        while fast and fast.next:
            tail=slow
            slow=slow.next
            fast=fast.next.next
        #split two list
        tail.next=None
        #divide 
        head1=self.sortList(head)
        head2=self.sortList(slow)
        return self.merge(head1,head2)
    
    def merge(self,head1,head2):
        dummy=ListNode(0)
        tail=dummy
        while head1 and head2:
            if head1.val<head2.val:
                tail.next=head1
                tail=tail.next
                head1=head1.next
            else:
                tail.next=head2
                tail=tail.next
                head2=head2.next
        tail.next=head1 if head1 else head2
        return dummy.next
        
if __name__=='__main__':
    head=ListNode(4)
    head.insert(2)
    head.insert(1)
    head.insert(3)
    print("Old  :",end='')
    head.printList() #Old  :[4, 2, 1, 3]

    result = Solution()
    ans = result.sortList(head)
    print("After:",end='')
    ans.printList() #After:[1, 2, 3, 4]

## C++:

#include<iostream>
#include<vector>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(): val(0), next(nullptr) {}
    ListNode(int x): val(x), next(nullptr) {}
    ListNode(int x, ListNode *next): val(x), next(next) {}
};

void InsertNode(ListNode *head, int data){
    ListNode *tail=head;
    if (tail->next==nullptr){
        ListNode *new_node= new ListNode(data);
        tail->next=new_node;
    }
    else
        InsertNode(tail->next,data);
}

void PrintList(ListNode *head){
    vector<int> res;
    ListNode *tail=head;
    while (tail!=nullptr){
        res.push_back(tail->val);
        tail=tail->next;
    }
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next)
            return head;
        ListNode *slow=head;
        ListNode *fast=head;
        ListNode *pre=nullptr;
        while (fast && fast->next){
            pre=slow;
            slow=slow->next;
            fast=fast->next->next;
        }
        pre->next=nullptr;
        ListNode *head1=sortList(head);
        ListNode *head2=sortList(slow);
        return mergeList(head1,head2);
    }
    ListNode *mergeList(ListNode *head1, ListNode *head2){
        ListNode *dummy=new ListNode(0), *tail=dummy;
        while (head1 && head2){
            if (head1->val < head2->val){
                tail->next=head1;
                tail=tail->next;
                head1=head1->next;
            }
            else{
                tail->next=head2;
                tail=tail->next;
                head2=head2->next;
            }
        }
        tail->next=(head1!=nullptr)? head1 :head2;
        return dummy->next;
    }
};

int main(){
    ListNode *head=new ListNode(4);
    InsertNode(head,2);
    InsertNode(head,1);
    InsertNode(head,3);
    cout<<"Original List: ";
    PrintList(head); //Original List: 4 2 1 3

    Solution res;
    ListNode *ans=res.sortList(head);
    cout<<"After Sorted : ";
    PrintList(ans); //After Sorted : 1 2 3 4

    return 0;
}