Merge Sort for Linked Lists | GeeksforGeeks
Merge Sort for Linked Lists Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible. Let head be the first node of the linked list to be sorted and headRef be the pointer to head. Note that we need a reference to head in MergeSort() as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at original head is not the smallest value in linked list.
http://www.programcreek.com/2012/11/leetcode-solution-merge-sort-linkedlist-in-java/
Break the list to two in the middle
Recursively sort the two sub lists
Merge the two sub lists
http://www.dontforgettothink.com/2011/11/23/merge-sort-of-linked-list/
https://gist.github.com/gcrfelix/e2e7ab52a542306234cc
http://www.cnblogs.com/springfor/p/3869372.html
2 if(head == null|| head.next == null)
3 return head;
4 ListNode slow = head, fast = head, firsthalf = head;
5 while(fast.next!=null&&fast.next.next!=null){
6 slow = slow.next;
7 fast = fast.next.next;
8 }
9 ListNode secondhalf = slow.next;
10 slow.next = null;
11
12 ListNode leftlist = null, rightlist =null;
13 if(firsthalf!=secondhalf){
14 leftlist = sortList(firsthalf);
15 rightlist = sortList(secondhalf);
16 }
17 return mergeTwoLists(leftlist, rightlist);
18 }
19
20 public ListNode mergeTwoLists(ListNode leftlist, ListNode rightlist){
21 if(rightlist == null)
22 return leftlist;
23 if(leftlist == null)
24 return rightlist;
25
26 ListNode fakehead = new ListNode(-1);
27 ListNode ptr = fakehead;
28 while(rightlist!=null&&leftlist!=null){
29 if(rightlist.val<leftlist.val){
30 ptr.next = rightlist;
31 ptr = ptr.next;
32 rightlist = rightlist.next;
33 }else{
34 ptr.next = leftlist;
35 ptr = ptr.next;
36 leftlist = leftlist.next;
37 }
38 }
39
40 if(rightlist!=null)
41 ptr.next = rightlist;
42 if(leftlist!=null)
43 ptr.next = leftlist;
44
45 return fakehead.next;
46 }
http://www.sanfoundry.com/java-program-implement-merge-sort-algorithm-linked-list/
Also check http://www.programcreek.com/2012/11/leetcode-solution-merge-sort-linkedlist-in-java/
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
Read full article from Merge Sort for Linked Lists | GeeksforGeeks
Merge Sort for Linked Lists Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible. Let head be the first node of the linked list to be sorted and headRef be the pointer to head. Note that we need a reference to head in MergeSort() as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at original head is not the smallest value in linked list.
http://www.programcreek.com/2012/11/leetcode-solution-merge-sort-linkedlist-in-java/
Break the list to two in the middle
Recursively sort the two sub lists
Merge the two sub lists
http://www.dontforgettothink.com/2011/11/23/merge-sort-of-linked-list/
https://gist.github.com/gcrfelix/e2e7ab52a542306234cc
http://www.cnblogs.com/springfor/p/3869372.html
考虑到要求用O(nlogn)的时间复杂度和constant space complexity来sort list，自然而然想到了merge sort方法。同时我们还已经做过了merge k sorted list和merge 2 sorted list。这样这个问题就比较容易了。
不过这道题要找linkedlist中点，那当然就要用最经典的faster和slower方法，faster速度是slower的两倍，当faster到链尾时，slower就是中点，slower的next是下一半的开始点。
1 public ListNode sortList(ListNode head) {2 if(head == null|| head.next == null)
3 return head;
4 ListNode slow = head, fast = head, firsthalf = head;
5 while(fast.next!=null&&fast.next.next!=null){
6 slow = slow.next;
7 fast = fast.next.next;
8 }
9 ListNode secondhalf = slow.next;
10 slow.next = null;
11
12 ListNode leftlist = null, rightlist =null;
13 if(firsthalf!=secondhalf){
14 leftlist = sortList(firsthalf);
15 rightlist = sortList(secondhalf);
16 }
17 return mergeTwoLists(leftlist, rightlist);
18 }
19
20 public ListNode mergeTwoLists(ListNode leftlist, ListNode rightlist){
21 if(rightlist == null)
22 return leftlist;
23 if(leftlist == null)
24 return rightlist;
25
26 ListNode fakehead = new ListNode(-1);
27 ListNode ptr = fakehead;
28 while(rightlist!=null&&leftlist!=null){
29 if(rightlist.val<leftlist.val){
30 ptr.next = rightlist;
31 ptr = ptr.next;
32 rightlist = rightlist.next;
33 }else{
34 ptr.next = leftlist;
35 ptr = ptr.next;
36 leftlist = leftlist.next;
37 }
38 }
39
40 if(rightlist!=null)
41 ptr.next = rightlist;
42 if(leftlist!=null)
43 ptr.next = leftlist;
44
45 return fakehead.next;
46 }
http://www.sanfoundry.com/java-program-implement-merge-sort-algorithm-linked-list/
public Node MergeSort(Node headOriginal)
{if (headOriginal == null || headOriginal.next == null)
return headOriginal;
Node a = headOriginal;
Node b = headOriginal.next;
while ((b != null) && (b.next != null))
{headOriginal = headOriginal.next;
b = (b.next).next;
}b = headOriginal.next;
headOriginal.next = null;
return merge(MergeSort(a), MergeSort(b));
}public Node merge(Node a, Node b)
{Node temp = new Node();
Node head = temp;
Node c = head;
while ((a != null) && (b != null))
{if (a.item <= b.item)
{c.next = a;
c = a;
a = a.next;
}else{c.next = b;
c = b;
b = b.next;
}}c.next = (a == null) ? b : a;
return head.next;
}
/* sorts the linked list by changing next pointers (not data) */void MergeSort(struct node** headRef){ struct node* head = *headRef; struct node* a; struct node* b; /* Base case -- length 0 or 1 */ if ((head == NULL) || (head->next == NULL)) { return; } /* Split head into 'a' and 'b' sublists */ FrontBackSplit(head, &a, &b); /* Recursively sort the sublists */ MergeSort(&a); MergeSort(&b); /* answer = merge the two sorted lists together */ *headRef = SortedMerge(a, b);}/* See http://geeksforgeeks.org/?p=3622 for details of this function */struct node* SortedMerge(struct node* a, struct node* b){ struct node* result = NULL; /* Base cases */ if (a == NULL) return(b); else if (b==NULL) return(a); /* Pick either a or b, and recur */ if (a->data <= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return(result);}/* UTILITY FUNCTIONS *//* Split the nodes of the given list into front and back halves, and return the two lists using the reference parameters. If the length is odd, the extra node should go in the front list. Uses the fast/slow pointer strategy. */void FrontBackSplit(struct node* source, struct node** frontRef, struct node** backRef){ struct node* fast; struct node* slow; if (source==NULL || source->next==NULL) { /* length < 2 cases */ *frontRef = source; *backRef = NULL; } else { slow = source; fast = source->next; /* Advance 'fast' two nodes, and advance 'slow' one node */ while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } } /* 'slow' is before the midpoint in the list, so split it in two at that point. */ *frontRef = source; *backRef = slow->next; slow->next = NULL; }}
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
Read full article from Merge Sort for Linked Lists | GeeksforGeeks
