CA 24 - Sort a Linked List using Merge Sort

Problem

Given the head of a linked list, the task is to sort the linked list using merge sort.

Output

Example 1
Output: 10 -> 20 -> 30 -> 40 -> 50 -> 60
Example 2
Output: 2 -> 5 -> 8 -> 9

My Approach

To solve this problem, I used merge sort.

First, I divide the linked list into two halves using slow and fast pointers.

Then I recursively sort both halves.

After sorting, I merge the two sorted lists into one.

This works because merge sort divides the problem into smaller parts and then combines them in sorted order.

This approach is efficient because:

It guarantees O(n log n) time complexity
It uses constant extra space by rearranging pointers
Code

def merge_sort(head):
    if not head or not head.next:
        return head

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

    mid = slow.next
    slow.next = None

    left = merge_sort(head)
    right = merge_sort(mid)

    return merge(left, right)

def merge(l1, l2):
    dummy = Node(0)
    tail = dummy
    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    if l1:
        tail.next = l1
    else:
        tail.next = l2

    return dummy.next