Merge Two Sorted Lists

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

Example:

Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

Solution:

The approach here is similar to the “merge” step in Merge Sort.

Time Complexity: O(m+n) where m and n are length of two linked lists.

Space Complexity: O(m+n) where m and n are length of two linked lists.

You can find more solutions to more questions here.

Add a comment if you need solution to a question which is not present in the blog and i will try to come up with a solution as soon as possible.

Happy Reading :D