Sort a Linked List

Write a method to sort a linked list.

Solution: use divide and concur,  in-place merge sort. See the solution to "Merge Two Sorted Lists". This function will call the merge function inside. First partition, then merge. Complexity: O(nlogn).

Java语言: SortLinkedList

01 public ListNode merge(ListNode l1, ListNode l2)
02 {
03     if(l1==null)
04         return l2;
05     if(l2==null)
06         return l1;
07   
08     ListNode head=null;
09     ListNode curr=null;
10     ListNode temp=null;
11     while(l1!=null && l2!=null)
12     {
13         temp= (l1.value<l2.value?l1:l2);
14         if(head==null)
15         {
16             head=temp;
17             curr=head;
18         }              
19         else
20         {
21             curr.next=temp;
22             curr=curr.next;
23         }          
24         if(temp==l1)
25         {
26             l1=l1.next;
27         }
28         else
29         {
30             l2=l2.next;
31         }
32     }
33     if(l1!=null)
34     {
35         curr.next=l1;
36     }
37     if(l2!=null)
38     {
39         curr.next=l2;
40     }
41   
42     return head;
43 }
44 
45 public ListNode mergeSort(ListNode head)
46 {
47     if(head==null || head.next==null)
48         return head;
49     ListNode runner=head.next.next;
50     ListNode walker=head;
51     //find the middle node, using two pointers
52     while(runner!=null&& runner.next!=null )
53     {
54         runner=runner.next.next;
55         walker=walker.next;
56     }
57   
58     //partition
59     ListNode right=walker.next;
60     walker.next=null;
61     ListNode left=head;
62 
63     left=mergeSort(left);
64     right=mergeSort(right);
65 
66     //merge
67     head=merge(left,right);
68     return head;      
69 }