#98 Sort List

题目描述：

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

Have you met this question in a real interview?  Yes Example

Given 1->3->2->null, sort it to 1->2->3->null.

Challenge 

Solve it by merge sort & quick sort separately.

题目思路：

我用了merge sort的算法，这里因为这个题是linked list，和array sort有所不同：需要找到list的中间点，把list均匀分成两部分（注意要把中间点断掉）。找到以后就各自mergesort一番，再把两个sorted lists merge一下就好了（这里merge也用了好用的dummy head，就不用纠结merge好的list用list1做head还是list2做head了）。

Mycode（AC = 60ms）：

/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: You should return the head of the sorted linked list, using constant space complexity. */ ListNode *sortList(ListNode *head) { // write your code here return mergeSortList(head); } ListNode *mergeSortList(ListNode *head) { if (head == NULL || head->next == NULL) { return head; } // find the middle of list ListNode *slow = head, *fast = head; while (fast && fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } // evenly break the list into two lists ListNode *head2 = slow->next; slow->next = NULL; ListNode *list1 = mergeSortList(head); ListNode *list2 = mergeSortList(head2); return merge(list1, list2); // merge two sorted lists } // merge two sorted lists ListNode *merge(ListNode *head1, ListNode *head2) { ListNode *dummy = new ListNode(0); ListNode *tmp = dummy, *h1 = head1, *h2 = head2; while (h1 && h2) { if (h1->val <= h2->val) { tmp->next = h1; h1 = h1->next; tmp = tmp->next; } else { tmp->next = h2; h2 = h2->next; tmp = tmp->next; } } if (h1) tmp->next = h1; if (h2) tmp->next = h2; return dummy->next; } };