Given a reference to the head of a linked list, the task is to sort the linked list using the Merge Sort algorithm.
Note: When splitting the linked list, the extra node should be included in the first half if the number of nodes is odd.
Example 1
Input: LinkedList: 15 -> 10 -> 5 -> 20 -> 3
Output: 3 -> 5 -> 10 -> 15 -> 20
Explanation: The Merge Sort algorithm sorts the nodes in ascending order, resulting in 3 -> 5 -> 10 -> 15 -> 20.
Example 2
Input: LinkedList: 9 -> 7 -> 8 -> 6 -> 5
Output: 5 -> 6 -> 7 -> 8 -> 9
Explanation: The linked list is split into smaller parts, sorted, and merged to form the sorted list 5 -> 6 -> 7 -> 8 -> 9.
Approach, complexity and clean code in every language. Sign in to unlock the editorial.
Your submissions, results and runtime history live here. Sign in to start your streak.
15 10 5 20 3
3 5 10 15 20
9 7 8 6 5
5 6 7 8 9