Sort a Linked List Using Merge Sort

Given the head pointer of a linked list, sort the linked list in ascending order using merge sort and return the new head pointer of the sorted linked list.

Statement

Merge sort is one of the standard sorting algorithms for a linked list. If the given linked list is 29>23>82>1129 -> 23 -> 82 -> 11, then the sorted (in ascending order) list should be 11>23>29>8211 -> 23 -> 29 -> 82.

Example

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.