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.

Return the head of the merged linked list.

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 = [0]

Output: [0]

  • 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, 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 and return
  • 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.

comments powered by Disqus

Related Posts

Reverse Linked List

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.

Read more

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.

Read more

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.

Read more