## Saturday, 27 March 2021

### Java Program To Sort A Linked List

Here is the fully working Java code solution for sorting a Linked List. You can find the same problem as an exercise in LeetCode. I have used Merge Sort here. The expectation here is that the code should run in O(n log n) time complexity and space complexity should be O(1).

The below java program manages to do it within the same complexity limit.

If you see the code, we are dividing the LinkedList in halves with each recursive call. So recursion tree height would be log n. For each of these recursive step, we are finding the middle element of the current linked list which requires a full traversal. So it would be O(n). And we are merging sub lists in each recursive step which will again take O(n) (our merge() method is linear complexity). So worst case time complexity is (n + n) * log n = O(n logn).

Regarding space complexity, I am not creating any additional Linked List for merging and doing the merge in place by changing the pointers. Only four additional variables are used in merge step and that is fixed. So if we omit the space taken by recursion stack, we are using constant space. So space complexity is O(1).
/**
* 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 {
}

}
ListNode nextToMiddle = middle.next;
middle.next = null;
//sort left hand side array
//sort right hand side array
}

public ListNode merge(ListNode left, ListNode right){

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;
}
}

while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}