NUHMAN.com

Introduction

When tasked with sorting a singly linked list, we need an efficient algorithm. Unlike arrays, where random access is fast, linked lists are better suited to algorithms like merge sort due to their sequential access pattern.

In this problem, we’ll implement merge sort to sort a singly linked list in O(n log n) time with constant space complexity.

Problem Statement

Sort a linked list in O(n log n) time using constant space.

go

type ListNode struct {
    Val  int
    Next *ListNode
}

Approach: Merge Sort for Linked List

Merge Sort follows a divide and conquer strategy:

1. Divide the list into two halves.
2. Recursively sort each half.
3. Merge the two sorted halves.

Steps:

1. Use the fast and slow pointer method to split the list into two halves.
2. Recursively call sortList on each half.
3. Merge the two sorted halves using a helper merge function.

Go Implementation

go

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    // Split list into halves
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    mid := slow.Next
    slow.Next = nil

    left := sortList(head)
    right := sortList(mid)

    return merge(left, right)
}

func merge(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    curr := dummy

    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            curr.Next = l1
            l1 = l1.Next
        } else {
            curr.Next = l2
            l2 = l2.Next
        }
        curr = curr.Next
    }

    if l1 != nil {
        curr.Next = l1
    } else {
        curr.Next = l2
    }

    return dummy.Next
}

Time and Space Complexity

OperationComplexityTimeO(n log n)SpaceO(log n) stack (recursion)

• Time: Each merge step takes O(n), and there are log(n) levels of recursion.
• Space: Only recursive stack space, no extra data structures.

Example

Input:

rust

4 -> 2 -> 1 -> 3

Output:

rust

1 -> 2 -> 3 -> 4

Why Merge Sort for Linked Lists?

• Doesn’t require random access like quicksort.
• Naturally supports splitting and merging via pointer manipulation.
• Efficient time complexity for large datasets.

Conclusion

Using merge sort, we can efficiently sort a linked list in-place with optimal time complexity. Understanding this technique is essential for interviews and system-level programming where linked list performance matters.