NUHMAN.com

Introduction

Sorting a singly linked list is a classic problem in data structures. In this problem, we are asked to sort a list using the insertion sort algorithm.

Insertion sort is a simple algorithm often used for small datasets, and it works particularly well when applied to linked lists due to their dynamic nature.

Problem Statement

Sort a singly linked list using insertion sort.

go

type ListNode struct {
    Val  int
    Next *ListNode
}

Approach

We use a dummy node to facilitate insertion operations and maintain a sorted portion of the list. For each node in the original list:

1. Traverse the sorted part to find the correct insertion point.
2. Insert the current node.
3. Move to the next node in the original list.

Steps:

• Use a dummy node (dummy) to simplify insertion at the head.
• Iterate over the original list using a curr pointer.
• For each node, find the position to insert in the sorted list.
• Insert by adjusting pointers.

Go Implementation

go

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

func insertionSortList(head *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}
    curr := head

    for curr != nil {
        prev := dummy
        nextTemp := curr.Next

        // Find the insertion point
        for prev.Next != nil && prev.Next.Val < curr.Val {
            prev = prev.Next
        }

        // Insert curr between prev and prev.Next
        curr.Next = prev.Next
        prev.Next = curr

        // Move to the next node
        curr = nextTemp
    }

    return dummy.Next
}

Time and Space Complexity

OperationComplexityTimeO(n²) in worst caseSpaceO(1) (in-place)

• Worst case: list is in reverse order.
• Best case (already sorted): O(n)

Example

Input:

rust

4 -> 2 -> 1 -> 3

Output:

rust

1 -> 2 -> 3 -> 4

Why Insertion Sort Fits Linked Lists

• Efficient insertion: No shifting, just pointer updates.
• No need for extra space.
• Simple implementation.

Conclusion

Insertion sort is a natural fit for linked lists. This problem is a good exercise in manipulating pointers and understanding in-place sorting mechanisms. While it's not the fastest for large datasets, it's useful for moderately sized or nearly sorted lists.