Problem of the day
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
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.
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.
7 8 -1
1 3 4 6 -1
1 3 4 6 7 8 -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
5 -1
1 3 6 10 -1
1 3 5 6 10 -1