153: Sort linked list

Given a linked list, return a sorted linked list. Sort for O(nlogn) time complexity

 

Example 1

Input:  2 -> 3 -> 1

Output: 1 -> 2 -> 3

Example 2

Input:  3 -> 2 -> 1

Output: 1 -> 2 -> 3