Sort a Linked List using Merge Sort

In this task, I worked on sorting a singly linked list efficiently.

Since linked lists don’t support random access, algorithms like quicksort aren’t ideal. So I used merge sort, which works perfectly with linked lists.

What I Did
I created a function sortList that:

• Takes the head of a linked list
• Sorts it using merge sort

• Returns the sorted linked list
  How I Solved It

• I used the divide and conquer approach:

• Split the list into two halves

• Recursively sort both halves

• Merge the sorted halves
  Step 1: Find the Middle

• I used two pointers:

• slow moves one step at a time

• fast moves two steps

• When fast reaches the end, slow will be at the middle.

• Then I split the list into two halves.

Step 2: Recursively Sort
I called sortList on both halves:
Left half
Right half
Each half gets sorted independently.

Step 3: Merge Two Sorted Lists
I used a helper function merge:
Compare nodes from both lists
Attach the smaller one to the result
Continue until one list is exhausted
Attach the remaining nodes

CODE:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def sortList(self, head):
        if not head or not head.next:
            return head

        slow, fast = head, head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        mid = slow.next
        slow.next = None  

        left = self.sortList(head)
        right = self.sortList(mid)

        return self.merge(left, right)

    def merge(self, l1, l2):
        dummy = ListNode(-1)
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next

        if l1:
            tail.next = l1
        else:
            tail.next = l2

        return dummy.next

How It Works:
The list is repeatedly divided into smaller parts
Each part is sorted individually
Then everything is merged back in sorted order

Time Complexity:
O(n log n) → splitting + merging
Space Complexity
O(log n) → due to recursion stack

Example:
Original:
4 → 2 → 1 → 3 → None
Sorted:
1 → 2 → 3 → 4 → None