#21

Easy

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Merge Two Sorted Lists

Merge two sorted linked lists by splicing nodes into one sorted list using linked-list pointer manipulation and recursion.

linked list recursion

Problem Statement

You are given the heads of two sorted linked lists, list1 and list2. Your task is to merge the two lists into one sorted list. The merged list should be created by splicing together the nodes of list1 and list2.

Return the head of the newly merged sorted linked list. The lists are sorted in non-decreasing order, and the nodes are to be merged efficiently by manipulating their pointers.

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: list1 = [], list2 = []

Output: []

Example details omitted.

Example 3

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

Output: [0]

Example details omitted.

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.

Solution Approach

Iterative Approach

Start with a dummy node, and iterate through both lists. At each step, compare the nodes from list1 and list2, appending the smaller node to the new list. This continues until all nodes from both lists are processed.

Recursive Approach

Using recursion, compare the first node of list1 with the first node of list2. Recursively merge the rest of the lists, choosing the smaller node first. The base case handles when either list is empty.

Time and Space Considerations

Both iterative and recursive approaches have similar time complexity of O(n + m), where n and m are the lengths of list1 and list2. Space complexity for the iterative approach is O(1), while the recursive approach uses O(n + m) space due to the call stack.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity for both approaches is O(n + m), where n and m are the lengths of the two lists. The space complexity for the iterative approach is O(1), while for recursion, it is O(n + m) because of the recursion stack.

What Interviewers Usually Probe

Look for understanding of pointer manipulation and its impact on time and space complexity.
Evaluate the candidate's grasp of recursion and how it compares to iteration in this context.
Assess the candidate's ability to handle edge cases, such as empty lists or lists of different lengths.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the case where one list is empty.
Incorrectly managing pointer updates when merging nodes.
Not optimizing for space by using an iterative approach when recursion could lead to stack overflow.

Follow-up variants

Merging more than two lists.
Merging lists of different sizes while maintaining performance.
Handling negative numbers or different data types in the nodes.

FAQ

How do I efficiently merge two sorted linked lists?

Use linked-list pointer manipulation, iterating through both lists and selecting the smaller node at each step, or apply recursion to merge them.

What is the time complexity of merging two sorted linked lists?

The time complexity is O(n + m), where n and m are the lengths of the two lists being merged.

Is recursion or iteration better for merging two sorted lists?

Both approaches have O(n + m) time complexity, but recursion uses additional space for the call stack, whereas iteration can be more space-efficient.

Can the iterative solution handle empty lists?

Yes, the iterative solution can handle empty lists by checking for null pointers before performing comparisons.

What happens if the lists have different lengths?

The algorithm continues comparing the remaining nodes of the longer list after one list is exhausted, efficiently merging the remaining nodes.

terminal

Solution

Solution 1: Recursion

First, we judge whether the linked lists $l_1$ and $l_2$ are empty. If one of them is empty, we return the other linked list. Otherwise, we compare the head nodes of $l_1$ and $l_2$:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        if list1 is None or list2 is None:
            return list1 or list2
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

Solution 2: Iteration

We can also use iteration to implement the merging of two sorted linked lists.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        if list1 is None or list2 is None:
            return list1 or list2
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

Continue Practicing

#24 swap nodes in pairs #25 reverse nodes in k group #2 add two numbers