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.
Sign in to write, run, and submit your solution against the full test suite.