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