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).

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