Sort a Linked List using Merge Sort

Problem Statement

Given the head of a singly linked list, sort the linked list using Merge Sort.

Constraints:

1 ≤ number of nodes ≤ 10⁵
0 ≤ node.data ≤ 10⁶
Example 1

Input:

40 -> 20 -> 60 -> 10 -> 50 -> 30

Output:

10 -> 20 -> 30 -> 40 -> 50 -> 60
Example 2

Input:

9 -> 5 -> 2 -> 8

Output:

2 -> 5 -> 8 -> 9
Why Merge Sort for Linked List?

Merge Sort is preferred for linked lists because:

It does not require random access.
It works efficiently with pointers.
Time Complexity is O(n log n).
Space Complexity is O(1) (excluding recursion stack).

Unlike arrays, quick sort is not efficient for linked lists due to lack of indexing.

Approach Overview

Merge Sort works in three main steps:

Find the middle of the linked list.
Divide the list into two halves.
Recursively sort both halves.
Merge the two sorted halves.
Step 1 – Finding the Middle

We use the slow and fast pointer method.

Slow moves 1 step.
Fast moves 2 steps.
When fast reaches end, slow will be at middle.
Step 2 – Divide the List

After finding middle:

Break the list into two halves.
Call mergeSort recursively on both halves.
Step 3 – Merge Two Sorted Lists

Compare nodes from both lists.
Attach the smaller node to result.
Repeat until one list finishes.

Python Implementation
class Solution:

def mergeSort(self, head):
    # Base case
    if not head or not head.next:
        return head

    # Step 1: Find middle
    middle = self.getMiddle(head)
    next_to_middle = middle.next
    middle.next = None

    # Step 2: Divide and sort
    left = self.mergeSort(head)
    right = self.mergeSort(next_to_middle)

    # Step 3: Merge sorted halves
    sorted_list = self.sortedMerge(left, right)

    return sorted_list


def getMiddle(self, head):
    if not head:
        return head

    slow = head
    fast = head.next

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

    return slow


def sortedMerge(self, left, right):
    if not left:
        return right
    if not right:
        return left

    if left.data <= right.data:
        result = left
        result.next = self.sortedMerge(left.next, right)
    else:
        result = right
        result.next = self.sortedMerge(left, right.next)

    return result

Dry Run Example

Input:

9 -> 5 -> 2 -> 8

Step 1:
Split into:

9 -> 5
2 -> 8

Step 2:
Split again:

9 | 5
2 | 8

Step 3:
Merge:

5 -> 9
2 -> 8

Final Merge:

2 -> 5 -> 8 -> 9
Time and Space Complexity

Time Complexity: O(n log n)

Each level divides list into halves.
Merging takes O(n).

Space Complexity: O(log n)

Due to recursion stack.
Why This Works Efficiently

Linked lists allow easy splitting and merging using pointer manipulation.

No extra array is needed.
No shifting of elements.
Only pointer adjustments.