Sort a Linked List using Merge Sort

Introduction

Sorting is a fundamental operation in programming.

While arrays can be sorted easily, linked lists require a different approach.
The most efficient way to sort a linked list is using Merge Sort, because it works well with linked structures.

Problem Statement

Given the head of a linked list,
sort the list using Merge Sort and return the sorted list.

Examples

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

Intuition

Merge Sort follows Divide and Conquer:

1. Divide list into two halves
2. Recursively sort both halves
3. Merge sorted halves

Approach (Merge Sort)

Algorithm Steps

• Find middle of list

  • Use slow & fast pointer

• Split list into two halves

• Recursively sort both halves

• Merge the two sorted lists

Code (Python)

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

# Merge two sorted lists
def merge(l1, l2):
    dummy = ListNode(0)
    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

    tail.next = l1 if l1 else l2
    return dummy.next

# Find middle of list
def get_middle(head):
    slow, fast = head, head.next

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

    return slow

def merge_sort(head):
    if not head or not head.next:
        return head

    mid = get_middle(head)
    right = mid.next
    mid.next = None

    left = merge_sort(head)
    right = merge_sort(right)

    return merge(left, right)

Step-by-Step Explanation

For 40 → 20 → 60 → 10 → 50 → 30:

• Split → [40,20,60] and [10,50,30]
• Recursively split further
• Merge sorted parts
• Final → sorted list

Complexity Analysis

• Time Complexity: O(n log n)
• Space Complexity: O(log n) (recursion stack)

Conclusion

Merge Sort is the most efficient and preferred method to sort linked lists.
It demonstrates divide-and-conquer and pointer manipulation techniques.