[LeetCode] Sort List

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

• 解题思路
  可以利用归并排序解决该问题。普通的归并排序算法时间复杂度为O(nlogn)，空间复杂度为O(n)，因为需要建立两个数组来存储原来数组的值，这两个数组的长度加起来恰好为原数组的长度。但是对于链表可以省去复制两个已经排好序的数组的操作，从而使空间复杂度达到O(1)。

• 实现代码

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/16 21:46
    *  @Status   : Accepted
    *  @Runtime  : 79 ms
******************************************************************/
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}

};

class Solution {
public:
    ListNode * getMiddleOfList(ListNode *head)
    {
        ListNode *p = head;
        ListNode *q = head;
        while(q->next != NULL && q->next->next != NULL)
        {
            p = p->next;
            q = q->next->next;
        }

        return p;
    }

    ListNode *mergeList(ListNode *head1, ListNode *head2)
    {
        ListNode *merge = new ListNode(-1);
        ListNode *tmp = merge;
        while(head1 != NULL && head2 != NULL)
        {
            if (head1->val <= head2->val)
            {
                tmp->next = head1;
                head1 = head1->next;
            }
            else
            {
                tmp->next = head2;
                head2 = head2->next;
            }
            tmp = tmp->next;
        }

        if(head1 == NULL)
        {
            tmp->next = head2;
        }
        else
        {
            tmp->next = head1;
        }

        return merge->next;
    }

    ListNode *sortList(ListNode *head) {
        if (head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode *middle = getMiddleOfList(head);
        ListNode *next = middle->next;
        middle->next = NULL;
        return mergeList(sortList(head), sortList(next));
    }
};

void print(ListNode *head)
{
    ListNode *tmp = head;
    while(tmp)
    {
        cout<<tmp->val<<" ";
        tmp = tmp->next;
    }
    cout<<endl;
}

int main()
{
    ListNode* head = new ListNode(-1);
    ListNode* node1 = new ListNode(8);
    head->next = node1;
    ListNode* node2 = new ListNode(5);
    node1->next = node2;
    ListNode* node3 = new ListNode(9);
    node2->next = node3;
    ListNode* node4 = new ListNode(0);
    node3->next = node4;
    ListNode* node5 = new ListNode(1);
    node4->next = node5;
    ListNode* node6 = new ListNode(3);
    node5->next = node6;
    ListNode* node7= new ListNode(6);
    node6->next = node7;
    ListNode* node8 = new ListNode(4);
    node7->next = node8;
    print(head);

    Solution s;
    s.sortList(head);
    print(head);
}