# Merge Two Sorted Linked Lists

Moderate
0/80
Average time to solve is 15m

## 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 )
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
``````
Console