Sort a Linked List using Merge Sort

Problem

Given the head of a linked list, sort it in ascending order using Merge Sort.

Example 1:

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

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

Example 2:

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

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

*Python Code *

class Solution:

# Function to sort the linked list using merge sort
def mergeSort(self, head):

    if head is None or head.next is None:
        return head

    mid = self.getMiddle(head)
    next_to_mid = mid.next
    mid.next = None

    left = self.mergeSort(head)
    right = self.mergeSort(next_to_mid)

    sorted_list = self.sortedMerge(left, right)

    return sorted_list


# Function to merge two sorted linked lists
def sortedMerge(self, a, b):

    if a is None:
        return b
    if b is None:
        return a

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

    return result

Input:

30 10 50 20 40 60

Output:

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

Input:

8 2 5 9

Output:

2 -> 5 -> 8 -> 9