【题目】

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

【分析】

单链表适合用归并排序，双向链表适合用快速排序。本题可以复用Merge Two Sorted Lists方法

【代码】

/*********************************
*   日期：2015-01-12
*   作者：SJF0115
*   题目: 148.Sort List
*   来源：https://oj.leetcode.com/problems/sort-list/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <climits>
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<<p->val<<" ";
        p = p->next;
    }//while
    cout<<endl;
    return 0;
}