148. 정렬 링크

O (n log n) 시간 복잡 도와 상수 급 공간 복잡 도 에서 링크 를 정렬 합 니 다.
예시 1:
입력: 4 - > 2 - > 1 - > 3 출력: 1 - > 2 - > 3 - > 4 예시 2:
입력: - 1 - > 5 - > 3 - > 4 - > 0 출력: - 1 - > 0 - > 3 - > 4 - > 5
병합 정렬 로 해결 하고 병합 정렬 은 두 가지 쓰기 가 있 기 때문에 두 가지 방법 이 있 습 니 다.방법 1: (교체 의 병합 정렬)

//              ，       cut and merge（        ）
/**
 * 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 *fast=head, *slow=head;
        while(!fast||!fast->next){ //     ，  slow    
            fast=fast->next->next;
            slow=slow->next;
        }
        ListNode *temp = slow->next;
        slow->next=NULL;
        return merge(sortList(head),sortList(temp)); //sortList()   /        ，   merge    
    }

    //    merge  ，  leetcode21   
    ListNode* merge(ListNode *l1,ListNode *l2){
        ListNode *dummyhead = new ListNode(0);
        ListNode *p=dummyhead;
        while(l1!=NULL && l2 !=NULL){
            if(l1->val<l2->val){
                p->next=l1;
                l1=l1->next;
                p=p->next;
            }
            else{
                p->next=l2;
                l2=l2->next;
                p=p->next;
            }
        }
        p->next=NULL;
        if(l1!=NULL) p->next=l1;
        if(l2!=NULL) p->next=l2;
        return dummyhead->next;
    }
};

방법 2: 재 귀적 인 병합 정렬 이지 만 한 사례 는 시간 을 초과 합 니 다. 본 문 제 는 상수 급 공간 복잡 도 를 요구 하기 때 문 입 니 다.

//              ，       cut and merge（        ）
/**
 * 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 *fast=head, *slow=head;
        while(!fast||!fast->next){ //     ，  slow    
            fast=fast->next->next;
            slow=slow->next;
        }
        ListNode *temp = slow->next;
        slow->next=NULL;
        return merge(sortList(head),sortList(temp)); //sortList()   /        ，   merge    
    }

    //    merge  ，  leetcode21   
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = merge(l1->next, l2);
            return l1;
        } else {
            l2->next = merge(l1, l2->next);
            return l2;
        }
    }
};