We will sort a linked list in optimal way here. We will use “LeetCode 148. Sort List” problem as an example & solve it using Java language. The problem statement is:
Given the head of a linked list, return the list after sorting it in ascending order.
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Input: head = [5, 6, 4, 2, 1, 3, 7] Output: [1, 2, 3, 4, 5, 6, 7]
As you can see, the expectation here is to sort the linked list in O(n log n) time complexity & O(1) space complexity. Let’s evaluate Merge Sort & Quick Sort, and figure out if they can satisfy both time & space complexity bounds.
Standard Merge Sort does sorting in O(n log n) worst time complexity. But its space complexity is O(n) as new array is used while merging the elements. Quick Sort space complexity is O(1) as it can do in-place sorting easily. Its average time complexity is O(n log n), but worst time complexity can go up to O(n ^ 2).
So none of them completely satisfy expected time & space complexity bounds. We would need to tweak the approach of the standard sorting algorithm. We will be using modified Merge Sort algorithm which will do in-place sorting of the linked list.
I have already explained standard Merge Sort algorithm previously. You can go through that post if you need reference. There I have used array as an example.
There are some basic differences how we would follow the steps while using an array & a linked list.
Space Complexity: In-place Merge Sort can be done for arrays also. But it might require shifting a lot of elements within the original array. It makes the logic a bit more complicated & also there is a performance hit due to shifting of elements within the array. So we prefer to use a new array & insert elements one by one there. In-place merging in linked list is simpler. We can do this by simply changing the next pointers of the original nodes. We can do that using few extra node variables as shown in the Java code at the bottom of the post. So space complexity becomes constant O(1).
Time Complexity: Time complexity of merging at each recursion level will still be O(n). There is no change in that. You can refer to my earlier post on Merge Sort & the diagram there. But dividing step will have an additional traversal to find the middle element of the linked list. We can find middle element of an array without traversal when we know the array length. But in singly linked list there is no other way except doing a traversal. Recursion tree length is log n (again refer to my previous Merge Sort post). Dividing at each recursion level will require traversal of total n elements. So dividing phase time complexity is O(n log n). We already know that merging phase time complexity is O(n log n). So total time complexity is O(2n log n) which is O(n log n) if we remove the constant. So this modified version of Merge Sort is still working in O(n log n) time complexity.
Here is the fully working Java code solution of the above LeetCode problem:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next)
* { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return mergeSort(head);
}
public ListNode mergeSort(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode middle = findMiddle(head);
ListNode nextToMiddle = middle.next;
middle.next = null;
//sort left hand side array
ListNode leftHead = mergeSort(head);
//sort right hand side array
ListNode rightHead = mergeSort(nextToMiddle);
return merge(leftHead, rightHead);
}
public ListNode merge(ListNode left, ListNode right){
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
ListNode leftTemp = left;
ListNode rightTemp = right;
int count = 0;
while(leftTemp != null && rightTemp != null){
if(leftTemp.val <= rightTemp.val){
tail.next = leftTemp;
leftTemp = leftTemp.next;
} else {
tail.next = rightTemp;
rightTemp = rightTemp.next;
}
tail = tail.next;
}
if(leftTemp == null){
tail.next = rightTemp;
} else {
tail.next = leftTemp;
}
return dummyHead.next;
}
public ListNode findMiddle(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}