Problem Explanation
You are given the head of a linked list.
Your task is to sort the linked list using Merge Sort.
Example:
- Input:
40 → 20 → 60 → 10 → 50 → 30 - Output:
10 → 20 → 30 → 40 → 50 → 60
Method Used: Merge Sort
Idea
Merge Sort works in three steps:
- Divide the linked list into two halves
- Recursively sort both halves
- Merge the sorted halves
Why This Method?
- Time complexity:
O(n log n) - Space complexity:
O(1)(no extra arrays) - Best sorting algorithm for linked lists
Python Code with Explanation
class Solution:
def mergeSort(self, head):
Defines the function.
if not head or not head.next:
return head
Base case:
If list is empty or has one node → already sorted.
mid = self.getMiddle(head)
Find the middle of the linked list.
next_to_mid = mid.next
mid.next = None
Split the list into two halves.
left = self.mergeSort(head)
Recursively sort the left half.
right = self.mergeSort(next_to_mid)
Recursively sort the right half.
sorted_list = self.merge(left, right)
Merge the two sorted halves.
return sorted_list
Return the final sorted list.
Helper Function: Find Middle
def getMiddle(self, head):
slow = head
fast = head.next
Use slow and fast pointers.
while fast and fast.next:
slow = slow.next
fast = fast.next.next
Move:
- slow → 1 step
- fast → 2 steps
return slow
Slow pointer gives middle.
Helper Function: Merge Two Sorted Lists
def merge(self, left, right):
Merge two sorted linked lists.
if not left:
return right
if not right:
return left
If one list is empty, return the other.
if left.data < right.data:
result = left
result.next = self.merge(left.next, right)
Pick smaller node from left.
else:
result = right
result.next = self.merge(left, right.next)
Pick smaller node from right.
return result
Return merged list.
Complete Code
class Solution:
def mergeSort(self, head):
if not head or not head.next:
return head
mid = self.getMiddle(head)
next_to_mid = mid.next
mid.next = None
left = self.mergeSort(head)
right = self.mergeSort(next_to_mid)
return self.merge(left, right)
def getMiddle(self, head):
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def merge(self, left, right):
if not left:
return right
if not right:
return left
if left.data < right.data:
result = left
result.next = self.merge(left.next, right)
else:
result = right
result.next = self.merge(left, right.next)
return result
Step-by-Step Example
Input:
40 → 20 → 60 → 10 → 50 → 30
Process:
- Split into halves
- Sort each half
- Merge sorted lists
Output:
10 → 20 → 30 → 40 → 50 → 60
Key Takeaway
Merge Sort is the most efficient way to sort linked lists because it avoids random access and works well with node-based structures.
Top comments (0)