Merge Two Sorted Linked Lists

Moderate
0/80
Average time to solve is 15m
310 upvotes
Asked in companies
AmazonCIS - Cyber InfrastructureUber

Problem statement

You are given two sorted linked lists. You have to merge them to produce a combined sorted linked list. You need to return the head of the final linked list.

Note:

The given linked lists may or may not be null.

For example:

If the first list is: 1 -> 4 -> 5 -> NULL and the second list is: 2 -> 3 -> 5 -> NULL

The final list would be: 1 -> 2 -> 3 -> 4 -> 5 -> 5 -> NULL
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of input contains the elements of the first linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

The second line of input contains the elements of the second linked list separated by a single space and terminated by -1.
Output Format:
Print the final linked list. The elements of the linked list must be separated by a single space and terminated by -1.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1 <= L <= 10^5
1 ≤ data ≤ 10^6 and data != -1

Where L is the number of nodes in either of the two Linked List.

Time Limit: 1 sec 

Follow-up:

Try to solve this problem in linear time complexity and constant space complexity.
Sample Input 1:
7 8 -1
1 3 4 6 -1
Sample Output 1:
1 3 4 6 7 8 -1
Explanation of Input 1:
In this testcase, the first list is: 7 -> 8 -> NULL
The second list is: 1 -> 3 -> 4 -> 6 -> NULL
The final list would be: 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> NULL
Sample Input 2:
5 -1
1 3 6 10 -1
Sample Output 2
1 3 5 6 10 -1
Hint

Take the smaller head of the two linked lists.

Approaches (2)
Recursive
  • Without loss of generality, let’s say the head of the first linked list is smaller than the head of the second linked list.
  • The current node would be the smaller of the two, i.e. the head of the first node, here.
  • We run a recursive function, pointing to the next element of the head of the first linked list.
  • If only one of the lists is empty, we return null.
  • If both the lists are empty, we return null.
Time Complexity

O(N + M), where N and M are the numbers of nodes in both linked lists. 

 

We will be reversing both linked lists once which will take linear time on both.

Space Complexity

O(N+M), where N and M are the numbers of nodes in both linked lists. 

 

Considering the recursive stack space.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Merge Two Sorted Linked Lists
Full screen
Console