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.