[148]排序链表

//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 
//
// 进阶： 
//
// 
// 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
// 
//
// 示例 2： 
//
// 
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 5 * 104] 内 
// -105 <= Node.val <= 105 
// 
// Related Topics 排序 链表 
// 👍 1011 👎 0

/*
* 148 排序链表
* 2021-02-27 10:22:35
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * 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) {
        int n = 0;
        for(auto p = head; p;p = p->next) n++;

        auto dummy = new ListNode(-1);
        dummy->next = head;

        for(int i = 1;i < n;i *= 2){
            auto cur = dummy;
            for(int j = 0;i + j < n;j += i * 2){
                auto first = cur->next;
                auto second = first;
                for(int k = 0;k < i;k++) second = second->next;

                int f = 0, s = 0;
                while(f < i && s < i && second){
                    if(first->val <= second->val){
                        cur->next = first;
                        cur = first;
                        first = first->next;
                        f++;
                    }else{
                        cur->next = second;
                        cur = second;
                        second = second->next;
                        s++;
                    }
                }
                while(f < i){
                    cur->next = first;
                    cur = first;
                    first = first->next;
                    f++;
                }
                while(s < i && right){
                    cur->next = second;
                    cur = second;
                    second = second->next;
                    s++;
                }
                cur->next = second; // after reverse second is the head
            }
        }
        return dummy->next;
    }
};

class Solution2 {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;

        auto slow = head, fast = head;

        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        auto newHead = slow->next;
        slow->next = nullptr;
        return merge(sortList(head), sortList(newHead));
    }

    ListNode* merge(ListNode* a, ListNode* b){
        auto dummy = new ListNode(-1);
        auto cur = dummy;

        while(a && b){
            if(a->val < b->val){
                cur->next = a;
                a = a->next;
            }else{
                cur->next = b;
                b = b->next;
            }
            cur = cur->next;
        }
        if(a) cur->next = a;
        if(b) cur->next = b;
        return dummy->next;
    }
};
//leetcode submit region end(Prohibit modification and deletion)