Merge Sort on a Linked List

Problem Statement

Given the head of a singly linked list, sort it using Merge Sort.

Examples:

Input:
10 -> 30 -> 20 -> 50 -> 40 -> 60

Output:
10 -> 20 -> 30 -> 40 -> 50 -> 60

Input:
9 -> 2 -> 5 -> 8

Output:
2 -> 5 -> 8 -> 9

Constraints:

Number of nodes: 1 ≤ n ≤ 10^5
Node values: 0 ≤ node->data ≤ 10^6
Expected time complexity: O(n log n)
Expected space complexity: O(log n) (due to recursion)
Approach

steps:

Base : If the list is empty or has only one node, it is already sorted.
Divide: Find the middle of the linked list using the slow and fast pointer technique and split it into two halves.
Conquer & Merge: Recursively sort both halves and merge them using a helper function that merges two sorted linked lists.

Python Code

class Solution:
# Function to merge two sorted linked lists
def merge(self, a, b):
if not a:
return b
if not b:
return a

    if a.data <= b.data:
        result = a
        result.next = self.merge(a.next, b)
    else:
        result = b
        result.next = self.merge(a, b.next)

    return result

# Function to find the middle of the linked list
def getMiddle(self, head):
    if not head:
        return head

    slow = head
    fast = head.next

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

    return slow

# Main function to sort linked list using merge sort
def mergeSort(self, head):
    # Base case: 0 or 1 node
    if not head or not head.next:
        return head

    # Step 1: Split the list into halves
    middle = self.getMiddle(head)
    next_to_middle = middle.next
    middle.next = None  # split the list

    # Step 2: Recursively sort the two halves
    left = self.mergeSort(head)
    right = self.mergeSort(next_to_middle)

    # Step 3: Merge the sorted halves
    sorted_list = self.merge(left, right)
    return sorted_list

Explanation

Finding the middle: The getMiddle() function uses slow and fast pointers. Slow moves one step, fast moves two steps. When fast reaches the end, slow points to the middle.
Merging lists: The merge() function merges two sorted linked lists recursively.
Recursive sorting: The mergeSort() function splits the list, sorts both halves, and merges them back together.