sortList-use merge sort

 

Sort List -- LeetCode

分类： LeetCode2014-03-14 08:16 9133人阅读 评论(21) 收藏 举报

leetcode排序面试递归链表

原题链接: http://oj.leetcode.com/problems/sort-list/ 
这道题跟Insertion Sort List类似，要求我们用O(nlogn)算法对链表进行排序，但是并没有要求用哪一种排序算法，我们可以使用归并排序，快速排序，堆排序等满足要求的方法来实现。对于这道题比较容易想到的是归并排序，因为我们已经做过Merge Two Sorted Lists，这是归并排序的一个subroutine。剩下我们需要做的就是每次找到中点，然后对于左右进行递归，最后用Merge Two Sorted Lists把他们合并起来。代码如下：

[java] view plaincopy

1. public ListNode sortList(ListNode head) {  
2.     return mergeSort(head);  
3. }  
4. private ListNode mergeSort(ListNode head)  
5. {  
6.     if(head == null || head.next == null)  
7.         return head;  
8.     ListNode walker = head;  
9.     ListNode runner = head;  
10.     while(runner.next!=null && runner.next.next!=null)  
11.     {  
12.         walker = walker.next;  
13.         runner = runner.next.next;  
14.     }  
15.     ListNode head2 = walker.next;  
16.     walker.next = null;  
17.     ListNode head1 = head;  
18.     head1 = mergeSort(head1);  
19.     head2 = mergeSort(head2);  
20.     return merge(head1, head2);  
21. }  
22. private ListNode merge(ListNode head1, ListNode head2)  
23. {  
24.     ListNode helper = new ListNode(0);  
25.     helper.next = head1;  
26.     ListNode pre = helper;  
27.     while(head1!=null && head2!=null)  
28.     {  
29.         if(head1.val<head2.val)  
30.         {  
31.             head1 = head1.next;  
32.         }  
33.         else  
34.         {  
35.             ListNode next = head2.next;  
36.             head2.next = pre.next;  
37.             pre.next = head2;  
38.             head2 = next;  
39.         }  
40.         pre = pre.next;  
41.     }  
42.     if(head2!=null)  
43.     {  
44.         pre.next = head2;  
45.     }  
46.     return helper.next;  
47. }  

不过用归并排序有个问题就是这里如果把栈空间算上的话还是需要O(logn)的空间的。对于其他排序算法，用兴趣的同学可以实现一下哈。
排序是面试中比较基础的一个主题，所以对于各种常见的排序算法大家还是要熟悉，不了解的朋友可以参见排序算法 - Wiki。特别是算法的原理，很多题目虽然没有直接考察排序的实现，但是用到了其中的思想，比如非常经典的topK问题，就用到了快速排序的原理，关于这个问题在Median of Two Sorted Arrays中有提到，有兴趣的朋友可以看看。