MERGE SORT ON A LINKED LIST

How I Understood Merge Sort on a Linked List
When I first saw this problem, I knew merge sort works for arrays, but I wasn’t sure how to apply it to linked lists.
After breaking it down, I realized merge sort is perfect for linked lists because we can split and merge efficiently without extra space for indexing.

** Problem**
Given the head of a singly linked list, sort the list using merge sort and return the sorted head.
Example:
Python
Input: 4 -> 2 -> 1 -> 3 -> None
Output: 1 -> 2 -> 3 -> 4 -> None

What I Noticed
Key observations:
Linked lists cannot access middle by index, so we use slow and fast pointers to find the middle
Merge sort works in divide and conquer manner:
Divide list into two halves
Recursively sort each half
Merge the sorted halves
Merging two sorted linked lists is efficient and done in-place.

** What Helped Me**
Breaking down the solution into three main steps:
Find the middle: Use slow and fast pointers
Recursively sort halves: Split at middle and call mergeSort on each half
Merge sorted halves: Use a helper sortedMerge function
This gives O(n log n) time and uses O(log n) recursion space.

Code (Python)
Python
class Solution:
def mergeSort(self, head):
# Base case: empty or single node
if not head or not head.next:
return head

    # Step 1: Find the middle of the list
    mid = self.getMiddle(head)
    next_to_mid = mid.next
    mid.next = None  # Break the list into two halves

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

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

def getMiddle(self, head):
    if not head:
        return head
    slow = head
    fast = head
    # Fast moves twice as fast as slow
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def sortedMerge(self, a, b):
    if not a:
        return b
    if not b:
        return a

    # Pick the smaller value and recurse
    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

Example Usage
Python

Linked list: 4 -> 2 -> 1 -> 3

head = Node(4)
head.next = Node(2)
head.next.next = Node(1)
head.next.next.next = Node(3)

solution = Solution()
new_head = solution.mergeSort(head)

Print sorted list

curr = new_head
while curr:
print(curr.data, end=" -> ")
curr = curr.next
print("None")
Output:
Plain text
1 -> 2 -> 3 -> 4 -> None

** Complexity**
Time: O(n log n) — divide and merge
Space: O(log n) — recursion stack

What I Learned
Merge sort works very well on linked lists because:
No extra array needed
Finding middle with slow/fast pointers is efficient
Merging two sorted lists is simple with recursion
It’s a classic divide-and-conquer algorithm for linked lists.

** Final Thought**
At first, I thought merge sort would be hard on linked lists.
Once I realized:
“Use slow/fast to split and recursively merge sorted halves”
…it became clear, elegant, and efficient.
This is a great example of recursive pointer manipulation in linked lists.