[LeetCode]148.Merge Two Sorted Lists

[LeetCode]148.Merge Two Sorted Lists

【題目】

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

【分析】

單鏈表適合用歸並排序，雙向鏈表適合用快速排序。本題可以復用Merge Two Sorted Lists方法

【代碼】

/*********************************
*   日期：2015-01-12
*   作者：SJF0115
*   題目: 148.Merge Two Sorted Lists
*   來源：https://oj.leetcode.com/problems/sort-list/
*   結果：AC
*   來源：LeetCode
*   博客：
**********************************/
#include 
#include 
using namespace std;

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;
        }//if
        // 定義兩個指針
        ListNode *fast = head,*slow = head;
        // 慢指針找到中間節點
        while(fast->next != NULL && fast->next->next != NULL){
            // 快指針一次兩步
            fast = fast->next->next;
            // 慢指針一次一步
            slow = slow->next;
        }//while
        // 從中間節點斷開
        fast = slow->next;
        slow->next = NULL;
        // 前段排序
        ListNode *left = sortList(head);
        // 後段排序
        ListNode *right = sortList(fast);
        // 前後段合並
        return mergeTwoLists(left,right);
    }
private:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *head = new ListNode(-1);
        for(ListNode *p = head;l1 != NULL || l2 != NULL;p = p->next){
            int val1 = (l1 == NULL) ? INT_MAX : l1->val;
            int val2 = (l2 == NULL) ? INT_MAX : l2->val;
            if(val1 <= val2){
                p->next = l1;
                l1 = l1->next;
            }//if
            else{
                p->next = l2;
                l2 = l2->next;
            }//else
        }//for
        return head->next;
    }
};

int main(){
    Solution solution;
    int A[] = {8,3,10,5,11,1,4};
    // 鏈表
    ListNode *head = new ListNode(A[0]);
    ListNode *p = head;
    for(int i = 1;i < 7;i++){
        ListNode *node = new ListNode(A[i]);
        p->next = node;
        p = node;
    }//for
    head = solution.sortList(head);
    // 輸出
    p = head;
    while(p){
        cout<val<<" ";
        p = p->next;
    }//while
    cout<