CA 24 - Sort a Linked List using Merge Sort

Problem
Sort a Linked List using Merge Sort
You are given the head of a singly linked list.
Your task is to sort the linked list using Merge Sort.

Examples
Input: 60 → 50 → 40 → 30 → 20 → 10
Output: 10 → 20 → 30 → 40 → 50 → 60
Input: 9 → 5 → 2 → 8
Output: 2 → 5 → 8 → 9

Approach

Merge Sort works very well for linked lists because it does not require random access.

Steps:

• Find the middle of the linked list (using slow and fast pointers)
• Split the list into two halves
• Recursively sort both halves
• Merge the two sorted halves

This divide-and-conquer approach ensures efficient sorting.

Complexity:
Time Complexity: O(n log n)
Space Complexity: O(log n) (due to recursion)

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


def getMiddle(head):
    slow = head
    fast = head.next

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

    return slow


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


def mergeSort(head):
    if not head or not head.next:
        return head
    mid = getMiddle(head)
    right = mid.next
    mid.next = None

    left = head

    left = mergeSort(left)
    right = mergeSort(right)

    return merge(left, right)
head = ListNode(9)
head.next = ListNode(5)
head.next.next = ListNode(2)
head.next.next.next = ListNode(8)

sorted_head = mergeSort(head)

curr = sorted_head
while curr:
    print(curr.val, end=" -> " if curr.next else "")
    curr = curr.next