Merge Sort for Linked Lists

Problem Statement :

Given the head of a linked list, return the list after sorting it in ascending order.

Constraints:

• The number of nodes in the list is in the range [0, 5 * 104].
• -105 <= Node.val <= 105

Solution:

First, check if the head is null or if the next element of the head is null, then we don’t have to do anything, just return the list.

if(head ==null || head.next== null) return head;

If not, then apply Merge Sort Algorithm:

public ListNode sortList(ListNode head) {
        if(head ==null || head.next== null) return head;
        ListNode left = head;
        ListNode mid = getMid(head);
        ListNode right = mid.next;
        mid.next =null;
        
        left = sortList(left);
        right = sortList(right);
        
        return merge(left,right);
        
    }

To divide the list into two halves we need to find the middle node of the list:

public ListNode getMid(ListNode head){
        if(head ==null || head.next== null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

The method used in this code to find the middle node is called Tortoise and Hare, in which we move TortoiseNode(Slow Node) by one step and Hare Node(Fast Node) by two steps, so when the Fast Node reaches the end the Slow Node will be in the middle of the list.

We will return the Slow Node to get the middle node.

Now, so we have both the list, we have to sort them, we will use recursion for that, First, we will sort the left portion of the list and then the right one.

Then we have to merge them, for merging we will start with the node having smaller values then we move to the next node out of two having a smaller value till we get to the end of the lists

public ListNode merge(ListNode l,ListNode r){
        if(l ==null ) return r;
        if(r ==null ) return l;
        ListNode m=null;
        if(l.val<=r.val){
            m = l;
            l = l.next;
        }else{
            m = r;
            r = r.next;
        }
        ListNode node = m;
        while(l!=null&&r!=null){
            if(l.val<=r.val){
                m.next = l;
                l = l.next;
            }else{
                m.next = r;
                r = r.next;
            }
            m=m.next;
        }
        if(l!=null){
            m.next = l;
        }else{
            m.next = r;
        }
        return node;
    }

Then we returned the merged list to get the Sorted list as an output.

References :
1) Geeks For Geeks
2) Sort List — Merge Sort — Leetcode 148
3) Leetcode Discussion

Feel free to reach me out for any suggestion and queries, ping me on:
-[LinkedIn]
-[GitHub]
-[Twitter]