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:

1. Split the list into two halves
2. Recursively sort both halves
3. 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