Sort List

Introduction

Given the head of a linked list, return the list after sorting it in ascending order.

Solutions

1. Using Merge Sort

Merge Sort is a divide-and-conquer algorithm that efficiently sorts a linked list in $O(nlogn)$ time complexity. The algorithm works as follows:

Divide: Split the linked list into two halves until each sublist contains a single element.
Conquer: Recursively sort each sublist.
Combine: Merge the sorted sublists to produce a single sorted list.

The linked list is split using the fast and slow pointer technique, which ensures the list is divided into two nearly equal halves. The merging process involves comparing the nodes of the two lists and rearranging them to form a sorted list.

main.py

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    if l1 and l2:
        if l1.val > l2.val:
            # Swap l1 and l2 to ensure l1 has the smaller element
            l1, l2 = l2, l1
        # Recursively merge the remaining elements
        l1.next = merge_two_lists(l1.next, l2)
    # Return the non-null list or the merged list
    return l1 or l2

def sort_list(head: Optional[ListNode]) -> Optional[ListNode]:
    if not (head and head.next):
        # Base case: If the list is empty or has only one element, it's already sorted
        return head

    # Split the list into two halves using the fast and slow pointer technique
    half, slow, fast = None, head, head
    while fast and fast.next:
        half, slow, fast = slow, slow.next, fast.next.next

    # Split the list into two parts
    half.next = None

    # Recursively sort both halves
    l1 = sort_list(head)
    l2 = sort_list(slow)

    # Merge the sorted halves
    return merge_two_lists(l1, l2)

Introduction

Solutions

1. Using Merge Sort

References