LeetCode 101: 21 Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a 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:

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

Example:

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

Example:

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

问题

给定两个已排序的链表 list1 和 list2 的头节点。

将这两个链表合并为一个有序链表。合并后的链表应该通过拼接前两个链表的节点组成。

返回合并后链表的头节点。

解决方案 1

迭代法

Approach 1 / 方法 1

This solution uses an iterative approach to merge the two linked lists. We maintain a dummy node to simplify the edge cases and a tail pointer to build the merged list by choosing the smaller node from list1 and list2 at each step.

该解决方案使用迭代方法来合并两个链表。我们使用一个 dummy 节点来简化边界情况，并使用一个 tail 指针通过选择 list1 和 list2 中较小的节点来构建合并后的链表。

Implementation / 实现

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = ListNode(0)
        tail = dummy

        while list1 and list2:
            if list1.val < list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next

        tail.next = list1 if list1 else list2

        return dummy.next

Explanation / 解释

1. Initialize dummy and tail Nodes / 初始化 dummy 和 tail 节点

   dummy = ListNode(0)
   tail = dummy

   • English: We initialize a dummy node with a value of 0 and set the tail pointer to the dummy node. The dummy node helps us easily return the head of the merged list.
   • Chinese: 我们初始化一个值为 0 的 dummy 节点，并将 tail 指针设置为 dummy 节点。dummy 节点帮助我们轻松返回合并链表的头节点。

2. Iterate Over Both Lists / 遍历两个链表

   while list1 and list2:

   • English: We enter a loop that continues as long as both list1 and list2 are not None.
   • Chinese: 我们进入一个循环，只要 list1 和 list2 都不为 None，循环就会继续。

3. Compare the Current Nodes of list1 and list2 / 比较 list1 和 list2 的当前节点

   if list1.val < list2.val:
      tail.next = list1
      list1 = list1.next
   else:
      tail.next = list2
      list2 = list2.next

   • English: We compare the values of the current nodes in list1 and list2. The smaller value is attached to the tail of the merged list, and we move the corresponding list's pointer forward.
   • Chinese: 我们比较 list1 和 list2 中当前节点的值。将较小的值附加到合并链表的 tail 上，并将相应链表的指针向前移动。

4. Move the tail Pointer Forward / 将 tail 指针向前移动

   tail = tail.next

   • English: We move the tail pointer forward to the newly added node in the merged list.
   • Chinese: 我们将 tail 指针向前移动到合并链表中新添加的节点。

5. Attach the Remaining Nodes / 附加剩余的节点

   tail.next = list1 if list1 else list2

   • English: Once we reach the end of one list, we attach the remaining nodes of the other list to the merged list. This handles the case where one list is longer than the other.
   • Chinese: 一旦我们到达其中一个链表的末尾，我们将另一个链表的剩余节点附加到合并后的链表上。这处理了一个链表比另一个链表长的情况。

6. Return the Head of the Merged List / 返回合并链表的头节点

   return dummy.next

   • English: Finally, we return dummy.next, which points to the head of the merged list.
   • Chinese: 最后，我们返回 dummy.next，它指向合并链表的头节点。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n + m), where n is the length of list1 and m is the length of list2. We traverse each list exactly once.
• Space Complexity / 空间复杂度: O(1), since we are using only a constant amount of extra space for the pointers.

Key Concept / 关键概念

• Merging Two Lists / 合并两个链表: The iterative approach efficiently merges two sorted linked lists into one sorted list by comparing nodes and adjusting pointers.
• 合并两个链表: 迭代方法通过比较节点并调整指针，高效地将两个已排序的链表合并为一个有序链表。

Simplify the code

dummy = tail = ListNode(0)

while list1 and list2:
    if list1.val < list2.val:
        tail.next, list1 = list1, list1.next
    else:
        tail.next, list2 = list2, list2.next
    tail = tail.next

tail.next = list1 or list2

return dummy.next

解决方案 2

递归法

Approach 2 / 方法 2

This solution uses recursion to merge the two linked lists. The idea is to recursively compare the current nodes of both lists, attach the smaller node to the merged list, and proceed with the next nodes.

该解决方案使用递归方法来合并两个链表。其思想是递归地比较两个链表的当前节点，将较小的节点附加到合并后的链表上，并继续处理下一个节点。

Implementation / 实现

python

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        if not list1:
            return list2
        if not list2:
            return list1

        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

Explanation / 解释

1. Base Cases: Handle Empty Lists / 基本情况：处理空链表

   if not list1:
      return list2
   if not list2:
      return list1

   • English: If either list1 or list2 is empty, we return the non-empty list as the result.
   • Chinese: 如果 list1 或 list2 为空，我们返回非空链表作为结果。

2. Compare the Current Nodes of list1 and list2 / 比较 list1 和 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

   • English: We compare the values of the current nodes in list1 and list2. The smaller value becomes the head of the merged list, and we recursively call mergeTwoLists to merge the rest of the lists.
   • Chinese: 我们比较 list1 和 list2 中当前节点的值。较小的值成为合并链表的头节点，我们递归调用 mergeTwoLists 来合并剩余的链表。

3. Recursive Step: Merge the Remaining Nodes / 递归步骤：合并剩余的节点

   • English: The function continues to recursively merge the remaining nodes of the two lists until one list is exhausted.
   • Chinese: 该函数继续递归合

并两个链表的剩余节点，直到一个链表耗尽。

4. Return the Head of the Merged List / 返回合并链表的头节点
   • English: The base case returns the head of the merged list once all nodes have been processed.
   • Chinese: 基本情况返回合并链表的头节点，一旦所有节点都已处理。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n + m), where n is the length of list1 and m is the length of list2. Each node is processed exactly once.
• Space Complexity / 空间复杂度: O(n + m), due to the recursion stack, which will hold up to n + m calls in the worst case.

Key Concept / 关键概念

• Recursive Merging / 递归合并: The recursive approach is elegant and straightforward, particularly when dealing with linked lists. It takes advantage of the natural recursive structure of the problem.
• 递归合并: 递归方法优雅且直观，特别是在处理链表时。它利用了问题的自然递归结构。

Comparison / 比较

1. Efficiency / 效率:

   • Iterative Approach / 迭代方法: More efficient in terms of space, with O(1) space complexity.
   • Recursive Approach / 递归方法: Easier to understand and implement for some, but with O(n + m) space complexity due to recursion.

2. Use Case / 使用场景:

   • Iterative / 迭代: Preferred when memory usage is a concern, especially for very large lists.
   • Recursive / 递归: Preferred for its simplicity and ease of understanding, especially for smaller lists.

Summary / 总结

• English: Both the iterative and recursive approaches are valid for merging two sorted linked lists. The iterative method is more space-efficient, while the recursive method is more elegant and simple.
• Chinese: 迭代和递归方法都是合并两个已排序链表的有效方法。迭代方法在空间上更高效，而递归方法在代码上更优雅和简单。

Tips / 提示

• English: Choose the iterative approach for larger lists to avoid stack overflow due to recursion.
• Chinese: 对于较大的链表，选择迭代方法以避免由于递归引起的栈溢出。

Solution Template for Similar Questions / 提示

• English: Use the iterative approach for in-place modifications and the recursive approach for problems that naturally fit recursion, especially in tree or linked list problems.
• Chinese: 对于就地修改的场景，使用迭代方法；对于自然适合递归的问题，特别是在树或链表问题中，使用递归方法。

5 More Similar Questions / 推荐5问题

1. LeetCode 23. Merge k Sorted Lists
2. LeetCode 92. Reverse Linked List II
3. LeetCode 148. Sort List
4. LeetCode 86. Partition List
5. LeetCode 328. Odd Even Linked List

Recommended Resources / 推荐资源

• English: Practice merging linked lists with both iterative and recursive methods to strengthen your understanding of linked list manipulation.

• Chinese: 通过迭代和递归方法练习合并链表，以加深对链表操作的理解。

• Merge Two Sorted Lists - Leetcode 21 - Python by NeetCode
  

• LeetCode #21: Merge Two Sorted Lists (Visualization) by Algo Engine