# Merge Two Sorted Linked Lists

Posted: 27 Oct, 2020

Difficulty: Moderate

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

##### Input Format:

```
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Then the test case follows.
The first line of each test case 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 each test case contains the elements of the second linked list separated by a single space and terminated by -1.
```

##### Output Format:

```
For each test case, print the final linked list. The elements of the linked list must be separated by a single space and terminated by -1.
Print output of each test case in a separate line.
```

##### Note:

```
You are not required to print the expected output, it has already been taken care of. Just implement the function.
```

##### Constraints:

```
1 <= T <= 10
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.
```

Approach 1

- 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.

Approach 2

- If one of the given lists is NULL, return the head of the other list.
- The data of the head of the first node should be less than or equal to the data of the head of the second node.
- Traverse both the linked lists simultaneously.
- If the current node of the second linked list is smaller than the current node of the first linked list, insert the current node of the second linked list before the current node of the first linked list.
- This is done by making the next node of the previous node of the first linked list as the current node of the second linked list. Further, make the next node of this node as the current node of the first linked list.
- If the first list has reached the end and the second list hasn’t, point its next node to the head of the second list.

SIMILAR PROBLEMS

# Vertical Sum in BST

Posted: 27 Jul, 2021

Difficulty: Moderate

# Reverse A LL

Posted: 9 Sep, 2021

Difficulty: Moderate

# Remove Duplicates From Sorted List

Posted: 21 Sep, 2021

Difficulty: Easy

# Binary Linked List To Integer

Posted: 22 Sep, 2021

Difficulty: Easy

# Intersection of Linked Lists

Posted: 12 Dec, 2021

Difficulty: Easy