CA 24 - Sort a Linked List using Merge Sort

1.Problem Understanding (Don’t skip this)

Given problem statement is the head of a linked list and to sort it by using merge sort.

2.Core Idea
Step 1: Find the middle
Use slow and fast pointer
Slow → moves 1 step
Fast → moves 2 steps
Step 2: Split the list
Cut the list into two halves
code:
mid.next = None
Step 3: Merge two sorted lists
4.Example:
40 → 20 → 60 → 10 → 50 → 30
Split:
[40 → 20 → 60] [10 → 50 → 30]
Further split:
[40] [20 → 60]
[10] [50 → 30]
Then merge step-by-step:
[20 → 60]

[10 → 50 → 30] → sorted → [10 → 30 → 50]
Final:
10 → 20 → 30 → 40 → 50 → 60
5.Algorithm
If list has 0 or 1 node → return
Find middle
Split list
Recursively sort left and right
Merge both