Leetcode--Sort List

Leetcode--Sort List

Problem Description:

Sort a linked list in O(n log n) time using constant space complexity.

分析：對鏈表進行排序，思考排序算法時間復雜度為O(nlogn)的只有歸並，快排和堆排序，應用到鏈表上的歸並比較合適，這裡利用快慢指針找到鏈表的中間節點，然後分別對兩邊遞歸歸並排好序後將兩邊歸並即可得到最終有序序列。具體代碼如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(!head||!head->next)
            return head;

        ListNode *p=head,*q=head,*r=NULL,*newhead=NULL;

        while(q&&q->next!=NULL)
        {
            r=p;
            p=p->next;
            q=q->next->next;
        }
        
        q=r->next;//找到另一半的起始節點
        r->next=NULL;
        p=head;
        
        p=sortList(p);
        q=sortList(q);
        
        if(p&&q)
        {
            if(p->val<=q->val)//先初始化頭結點
            { 
                newhead=r=p; 
                p=p->next; 
            }
            else 
            { 
                newhead=r=q; 
                q=q->next; 
            }
        
            //merge p and q
            while(p&&q)
            {
            if(p->val<=q->val)
            {
                r->next=p;
                r=p;
                p=p->next;
            }
            else
            {
                r->next=q;
                r=q;
                q=q->next;
            }
            }
        } 
        
        if(p)
            r->next=p;
        if(q)
            r->next=q;

        return newhead;
    }
};