###### tags: `LeetCode` `Linked List` `Medium` `Merge Sort`
# LeetCode #148 [Sort List](https://leetcode.com/problems/sort-list/) - Advanced
### (Medium)

給你鏈結串列的頭結點 head，請將其按 升序 排列並返回排序後的鏈結串列。


---
依照題目要求, 需在時間複雜度O(nlogn), 空間複雜度O(1)的情況下完成。


可以看到, 唯一能滿足的方法只有bottom up的merge sort。

使用split搭配for迴圈:
* for迴圈初始為i=1, 每次遞迴後i<<=1, 代表i左移一格(乘以2)。
* split函式的參數為(ListNode* head, int n), n代表這串鍊結串列的長度, 也就是說以head開始往後數n個節點, 宣告一指標指向該節點下一個元素後, 將該節點的next指向nullptr(也就是斷開節點), 然後回傳新宣告的指標。

比如說 3->2->4->1, n=2, split完後會變成3->2 & 4->1, 並返回指向4的指標。

然後將切完的節點傳入merge中, merge函式會進行排序(每次只要比較兩指標節點的第一個元素即可), 排序完後回傳pair<ListNode*, ListNode*>分別代表head指標與tail指標, 將指標頭尾相接後進行下一輪split&merge, 一次切割的數量大於整個鏈結串列的長度, 此時回傳指向鏈結串列第一個元素的指標即可。

---

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head||!head->next)return head;
        int len=1;
        ListNode* cur = head;
        while(cur){
            len++;
            cur=cur->next;
        }
        ListNode *l, *r, *tail;
        ListNode dummy(0);
        dummy.next = head;
        for(int n=1;n<len;n<<=1){
            cur=dummy.next;
            tail=&dummy;
            while(cur){
                l=cur;
                r=split(l, n);
                cur=split(r, n);
                auto merged = merge(l, r);
                tail->next=merged.first;
                tail=merged.second;
            }
        }
        return dummy.next;
    }
    ListNode* split(ListNode* head, int n){
        //return rest nodes' head
        while(--n&&head){
            head=head->next;
        }
        ListNode* rest = head?head->next:nullptr;
        if(head)head->next = nullptr;
        return rest;
    }
    pair<ListNode*, ListNode*> merge(ListNode* l1, ListNode* l2){
        //return head, tail
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while(l1&&l2){
            if(l1->val>l2->val)swap(l1,l2);
            tail->next = l1;
            l1=l1->next;
            tail = tail->next;
        }
        tail->next = l1?l1:l2;
        while(tail->next)tail=tail->next;
        return {dummy.next, tail};
    }
};