Merge Sort for Linked List

Problem Statement:
Given the head of a linked list, sort the list using Merge Sort.

Example:
Input: 40 → 20 → 60 → 10 → 50 → 30
Output: 10 → 20 → 30 → 40 → 50 → 60

Approach:
We use the Merge Sort algorithm:

• Split the linked list into two halves
• Recursively sort each half
• Merge the sorted halves
• To find the middle, we use slow and fast pointers. Code:

class Node:
def init(self, data):
self.data = data
self.next = None

def merge(left, right):
dummy = Node(0)
tail = dummy

while left and right:
    if left.data < right.data:
        tail.next = left
        left = left.next
    else:
        tail.next = right
        right = right.next
    tail = tail.next

tail.next = left if left else right
return dummy.next

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

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

return slow

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

middle = getMiddle(head)
next_to_middle = middle.next
middle.next = None

left = mergeSort(head)
right = mergeSort(next_to_middle)

return merge(left, right)

Explanation:
The list is divided recursively until single nodes remain. Then sorted lists are merged back together to form the final sorted list.

Time Complexity:
O(n log n)

Space Complexity:
O(log n) (recursion stack)