TIC
The Interns Company

Merge Two Sorted Lists

EasyAcceptance: 62.3%
Linked ListRecursion

Problem Statement

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Constraints:

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

Input Format:

  • Two linked lists l1 and l2

Output Format:

  • The merged sorted linked list

Examples:

Example 1:

Input:

l1 = [1,2,4], l2 = [1,3,4]

Output:

[1,1,2,3,4,4]

Explanation:

The two lists are merged to form a single sorted list.

Example 2:

Input:

l1 = [], l2 = []

Output:

[]

Explanation:

Both lists are empty, so the result is also empty.

Example 3:

Input:

l1 = [], l2 = [0]

Output:

[0]

Explanation:

When one list is empty, the result is the other list.

Solutions

Iterative Approach

Time: O(n + m) where n and m are the lengths of the two lists
Space: O(1) - only constant extra space is used

Use a dummy head and iterate through both lists, appending the smaller node.

Recursive Approach

Time: O(n + m) where n and m are the lengths of the two lists
Space: O(n + m) - due to the recursion stack

Recursively determine which list has the smaller head, and merge the remainder.

Algorithm Walkthrough

Example input:

Step-by-step execution:

  1. l1 = [1,2,4], l2 = [1,3,4]
  2. Create dummy = -1, tail = dummy
  3. While loop iteration 1:
  4. Compare: 1 <= 1 is true
  5. tail.next = l1(1), l1 = [2,4], tail = 1
  6. While loop iteration 2:
  7. Compare: 2 > 1 is true
  8. tail.next = l2(1), l2 = [3,4], tail = 1
  9. While loop iteration 3:
  10. Compare: 2 <= 3 is true
  11. tail.next = l1(2), l1 = [4], tail = 2
  12. While loop iteration 4:
  13. Compare: 4 > 3 is true
  14. tail.next = l2(3), l2 = [4], tail = 3
  15. While loop iteration 5:
  16. Compare: 4 <= 4 is true
  17. tail.next = l1(4), l1 = [], tail = 4
  18. l1 is null, so tail.next = l2 = [4]
  19. Result: dummy.next = [1,1,2,3,4,4]

Hints

Hint 1
Create a dummy head to simplify the code.
Hint 2
Compare the nodes from both lists and link the smaller one to the result list.
Hint 3
Try solving both iteratively and recursively.

Video Tutorial

Merge Two Sorted Lists - Iterative and Recursive Approaches

YouTube•Learn the Merge Two Sorted Lists solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the merging process as nodes are selected from each list and appended to the result list.

Key visualization elements:

  • current l1 node
  • current l2 node
  • merged list so far

Similar Questions

Merge k Sorted Lists

Hard

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Asked By

AmazonMicrosoftFacebookAppleGoogleLinkedIn

Implementation Notes

This problem is a classic linked list manipulation problem that tests your understanding of pointers and linked list operations. Both iterative and recursive approaches have their merits, with the iterative approach being more space-efficient.