Merge two sorted linked lists and return it as a new list.^{1}The new list should be made by splicing together the nodes of the first two lists.

It’s an easy problem in Leetcode for practicing linked list. It’s similar to the merge step of the Merge sort.

Brute force algorithm

Merge the both list together and sort the returning list. This will take complexitiy of @L O(n + m)log(n + m) @L , where n & m are length of each two list.

More efficient solution

Similary to algorithm used in merging step of Merge Sort, we can acheive @L O(n + m) @L time complexity. Traverse both the list together, and insert the smallest value into the new list.