Sort a Linked List using Merge Sort

Sorting a Linked List Using Merge Sort

Problem

You’re given the head of a linked list and asked to sort it using merge sort.

Strategy

I didn’t try to sort the list directly. That just made it confusing.

Instead, I broke it down into smaller steps:

• Find the middle of the list
• Split it into two halves
• Sort each half
• Merge them back together

So it’s really just:
split ,sort , merge

Code

class Solution:
    def mergeSort(self, head):
        if not head or not head.next:
            return head

        slow = head
        fast = head
        prev = None

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

        prev.next = None

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

        return self.merge(left, right)

    def merge(self, l1, l2):
        dummy = Node(0)
        current = dummy

        while l1 and l2:
            if l1.data < l2.data:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next

            current = current.next

        current.next = l1 if l1 else l2
        return dummy.next

Key Lines Explained

• if not head or not head.next:
  This is the base case. A list with one or zero nodes is already sorted.

• slow, fast, prev
  This is how I find the middle.
  prev helps me actually break the list into two parts.

• prev.next = None
  This line matters more than it looks.
  Without it, the list never splits, and recursion won’t work properly.

• self.mergeSort(head)
  Sorting the left half.

• self.mergeSort(slow)
  Sorting the right half.

• return self.merge(left, right)
  Combining two sorted halves into one.

Complexity

• Time: O(n log n)
• Space: O(log n) (due to recursion)

Final Note

This problem felt complicated at first, but breaking it down made it manageable.

It’s not really about linked lists — it’s about trusting the process:
split it, solve smaller parts, and put it back together.