In addition to Quicksort, merge sort is also a quite significant and classical sorting algorithm. Whereas partition is the most vital step of Quicksort, the most crucial step of merge sort is to merge two sorted (non-decreasing, typically) sequences into a sorted one.
For instance, if we have two sorted sequence {1, 3, 8}, {2, 9}, then the merged sequence would be {1, 2, 3, 8, 9}.
This is a partial-judged problem. Please implement the following function:
Where node is declared as:
The function would be called with the heads of the two sorted linked list.
It's guaranteed that the sum of the length of the linked lists would not exceed 2000000.
It should return the head of the merged linked list.