Sort List leetcode

Sort List leetcode

實現單鏈表排序 時間復雜度要求為 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==NULL||head->next==NULL)
            return head;
          
        ListNode *onestep=head;
        ListNode *twostep=head;//定義兩個指針，一個走一步，一個走兩步，用來找到中間節點
        
       // ListNode *first=NULL;
       // ListNode *second=NULL;
        
        while(twostep->next!=NULL&&twostep->next->next!=NULL)
        {
            onestep=onestep->next;
            twostep=twostep->next->next;
        }
        //此時onestep指向了整個鏈表的中間，如果偶數那麼兩邊均衡，如果為奇數，指向正中間需要從onestep出分開
        
        twostep=onestep;
        onestep=onestep->next;//此時onestep指向後半部分
        
        twostep->next=NULL;//將前半部分和後半部分分開
        
        twostep=sortList(head);
        onestep=sortList(onestep);
        
        return meger(twostep,onestep);
         
    }
    ListNode *meger(ListNode *first,ListNode *second)
    {
        ListNode *result;
        
        ListNode *p;
        
        if(first==NULL)
            return second;
        if(second==NULL)
            return first;
            
       //初始化result
        
        if(first->valval){
            result=first;
            first=first->next;
        }
        else
        {
            result=second;
            second=second->next;
        }
        p=result;
        
        while(first!=NULL&&second!=NULL)
        {
            if(first->valval)
            {
                p->next=first;
                first=first->next;
            }
            else
            {
                p->next=second;
                second=second->next;
            }
            p=p->next;
        }
        if(first!=NULL)
            p->next=first;
       else if(second!=NULL)
            p->next=second;
            
        return result;
    }
    
};