Merge Sort For linked List

In this task, I worked on sorting a linked list using Merge Sort.
Since linked lists don’t allow random access like arrays, Merge Sort is one of the best sorting algorithms for them.

MY APPROACH
I created a function that takes the head of a linked list and returns a sorted linked list using merge sort.

EXAMPLE
INPUT : 4 → 2 → 1 → 3 → NULL
OUTPUT : 1-> 2-> 3-> 4

LOGIC IMPLEMENTED
I used the divide and conquer method

• Find the middle of the list using slow & fast pointers
• Split the list into two halves
• Recursively sort each half
• Merge both sorted lists

How It Works

• The list is repeatedly divided into halves
• Each half is sorted individually
• Then both halves are merged in sorted order

class Solution:

    # Function to merge two sorted linked lists
    def merge(self, 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

        if left:
            tail.next = left
        if right:
            tail.next = right

        return dummy.next

    # Function to find middle of linked list
    def getMiddle(self, head):
        slow = head
        fast = head.next

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

        return slow

    # Main merge sort function
    def mergeSort(self, head):
        if not head or not head.next:
            return head

        # Step 1: Find middle
        mid = self.getMiddle(head)
        next_to_mid = mid.next
        mid.next = None

        # Step 2: Sort both halves
        left = self.mergeSort(head)
        right = self.mergeSort(next_to_mid)

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

        return sorted_list