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.

Comments

Popular posts from this blog

Longest Common Prefix

Roman To Integer

Two Sum