LeetCode 148.Sort List (排序链表)-蒲公英云

LeetCode 148.Sort List (排序链表)

题目描述：

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

AC C++ Solution:

归并排序:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//归并排序
/**
 * Merge sort use bottom-up policy, 
 * so Space Complexity is O(1)
 * Time Complexity is O(NlgN)
 * stable sort
*/
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(!head || !(head->next)) return head;
        //获得链表长度
        ListNode* cur = head;
        int length = 0;
        while(cur){
            length++;
            cur = cur->next;
        }
        ListNode dummy(0);
        dummy.next = head;
        ListNode *left, *right, *tail;
        for(int step = 1; step < length; step <<= 1){    //step成2的指数倍增加(1,2,4,8...)归并
            cur = dummy.next;
            tail = &dummy;
            while(cur){
                left = cur;                       //left第一个列表头部
                right = split(left, step);        //right第二个列表头部
                cur = split(right,step);          //再次分裂，cur为下次归并的头部
                tail = merge(left, right, tail);  //归并并返回归并后的尾部，作为下次归并的头
            }
        }
        return dummy.next;
    }
private:
    /*
     将链表分成两个列表，第一个包含前n个节点，返回第二个列表的头部
     */
    ListNode* split(ListNode *head, int n){
        //if(!head) return NULL;
        for(int i = 1; head && i < n; i++) head = head->next;
        if(!head) return NULL;
        ListNode *second = head->next;
        head->next = NULL;
        return second;
    }
      /*
      合并两个已排序的链表l1和l2,
      然后将合并的已排序链表追加到头节点
      然后合并排序链表的尾部
    */
    ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){
        ListNode *cur = head;
        while(l1 && l2){
            if(l1->val > l2->val){
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
            else{
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }
        }
        cur->next = (l1 ? l1 : l2);
        while(cur->next) cur = cur->next;
        return cur;
    }
};