 # Merge Two Sorted Lists

#### 1. Overview

In this article, we’re going to learn the different ways to merge two sorted lists.

#### 2. Description

Given the heads of two sorted linked lists list1 and list2, merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

###### Example 1:

`Input: list1 = [1,2,4], list2 = [1,3,4]`

`Output: [1,1,2,3,4,4]`

###### Example 2:

`Input: list1 = [], list2 = []`

`Output: []`

###### Example 3:

`Input: list1 = [], list2 = `

`Output: `

###### Constraints
• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

#### 3. Solution - Iterative Approach

• We’ll initialize two nodes: `prev` and `curr`. Node `prev` is the one used to return the final result, and the node `curr` is the one to help us merge the smaller node from the two lists.
• Then we’ll have a while loop to compare the two nodes: we’ll merge the smaller one to `curr.next`, and then move the smaller node and `curr` towards the right until either one of the two lists becomes `null`.
• When either one becomes `null`, we’ll assign the other non-null one to `curr.next` and return `prev.next`.
• Time complexity: O(M+N).

• Space complexity: O(1).

#### 4. Solution - Recursive Approach

• Two base cases: if `list1 == null`, we’ll return `list2`; if `list2 == null`, we’ll return `list1`.
• In other cases, (which means neither list1 nor list2 is null), if `list1.val` is smaller than `list2.val`, we’ll keep moving `list1` toward the right. In other cases, we’ll keep moving `list2` toward the right by keep making recursive calls.
• Time complexity: O(M+N).

• Space complexity: O(M+N).

#### 5. Conclusion

In this tutorial, we looked into merging two sorted lists using both iterative and recursive approaches.

Don’t just Leetcode, follow the Coding Patterns instead. Grokking The Coding Interview teaches you techniques and questions patterns to ace the coding interviews.

## Related Posts 1. Overview In this article, we’re going to learn the different ways to reverse a linked list. 2. Description Given the head of a linked list, reverse the list, and return the reversed list. ### Build REST API with Spring Boot and Kotlin

1. Overview In this article, we’re going to build a REST API using Spring Boot 2.x and Kotlin. Meanwhile, dedicated support for Kotlin was introduced since Spring Framework 5. ### How To Create a Spring Boot Project

1. Overview In this tutorial, we’ll look into the different ways we can create a Spring Boot project. 2. Using Spring Initializer in spring.