You are given the head of a singly linked list. Your task is to sort the linked list in non-decreasing order using the merge sort technique and return the head of the sorted linked list.
Example 1
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Explanation: The linked list is sorted in ascending order.
Example 2
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Explanation: The linked list is rearranged into non-decreasing order.
Example 3
Input: head = [1]
Output: [1]
Explanation: A single-node linked list is already sorted.
Sign in to write, run, and submit your solution against the full test suite.