CA 24 - Sort a Linked List Using Merge Sort

Problem Statement

You are given the head of a linked list. You have to sort the given linked list using Merge Sort.

Examples:

Input: 40 → 20 → 60 → 10 → 50 → 30
Output: 10 → 20 → 30 → 40 → 50 → 60

Input: 9 → 5 → 2 → 8
Output: 2 → 5 → 8 → 9

My Goal

For this problem, my goal was to:

Understand how merge sort works on linked lists
Divide the list into smaller parts
Merge sorted lists efficiently
Maintain optimal time complexity

My Approach & Solution

I used Merge Sort, which works perfectly for linked lists.

Idea:

Divide:
Find the middle of the list using slow and fast pointers
Split the list into two halves
Conquer:
Recursively sort both halves
Merge:
Merge two sorted linked lists

Solution Code (Python)

class ListNode:
    def __init__(s, v=0, n=None):
        s.val = v
        s.next = n

def merge(a, b):
    d = ListNode()
    c = d

    while a and b:
        if a.val < b.val:
            c.next = a
            a = a.next
        else:
            c.next = b
            b = b.next
        c = c.next

    c.next = a if a else b
    return d.next

def sortList(h):
    if not h or not h.next:
        return h

    # find middle
    s = h
    f = h.next

    while f and f.next:
        s = s.next
        f = f.next.next

    m = s.next
    s.next = None

    # sort halves
    l = sortList(h)
    r = sortList(m)

    return merge(l, r)

Explanation

Use slow/fast pointers to split list
Recursively sort left and right halves
Merge them using merge function
Repeat until fully sorted