Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
The Merge sort performs worst case O(N.LogN) unlike Quick Sort, which may have worst case O(N^2) if the random pivot element is chosen badly at each round.
How to Sort a Linked List using Merge Sort Algorithm?
To perform a merge sort, we may need to find the middle of the linked list. And this can be done via O(N) complexity via two pointers: fast and slow. The following is a modified version that records the previous pointer of the slow pointer so that we can split the linked list into two and return the middle pointer as the second half linked list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | ListNode* middle(ListNode* head) { if (head == NULL) return NULL; if (head->next == NULL) return NULL; ListNode* fast = head; ListNode* slow = head; ListNode* prev = NULL; while (fast && fast->next) { prev = slow; slow = slow->next; fast = fast->next->next; } // split into two prev->next = NULL; return slow; } |
ListNode* middle(ListNode* head) {
if (head == NULL) return NULL;
if (head->next == NULL) return NULL;
ListNode* fast = head;
ListNode* slow = head;
ListNode* prev = NULL;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
// split into two
prev->next = NULL;
return slow;
}We also need to merge two sorted linked list, which can be done using iterative approach by comparing the elements pointing to the two linked lists.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | ListNode* mergeList(ListNode* p1, ListNode* p2) { ListNode* dummy = new ListNode(-1); ListNode* head = dummy; while (p1 && p2) { if (p1->val < p2->val) { head->next = p1; p1 = p1->next; } else { head->next = p2; p2 = p2->next; } head = head->next; } if (p1) head->next = p1; if (p2) head->next = p2; return dummy->next; } |
ListNode* mergeList(ListNode* p1, ListNode* p2) {
ListNode* dummy = new ListNode(-1);
ListNode* head = dummy;
while (p1 && p2) {
if (p1->val < p2->val) {
head->next = p1;
p1 = p1->next;
} else {
head->next = p2;
p2 = p2->next;
}
head = head->next;
}
if (p1) head->next = p1;
if (p2) head->next = p2;
return dummy->next;
}Then, to sort a linked list using Merge Sort, we can recursively split the linked list into two, until each is one element only, then we can merge them bottom-up.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* sortList(ListNode* head) { if (head == NULL || head->next == NULL) return head; ListNode *mid = middle(head); head = sortList(head); mid = sortList(mid); return mergeList(head, mid); } }; |
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode *mid = middle(head);
head = sortList(head);
mid = sortList(mid);
return mergeList(head, mid);
}
};By using the Recursion, the space requirement is not constant i.e. O(N.LogN). The merge sort is one of the Divide-And-Conquer techniques that we repeatedly divide the problem into smaller ones until we can solve the sub-problems easily.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Merge k Sorted Lists using Recursive Divide and Conquer Algorithms?
Next Post: Using Recursive Backtracking Algorithm to Solve Classic N Queen Problem
