Algorithms 101: Merge Two Sorted Linked Lists

合并两个有序链表

Merging two sorted linked lists is a common problem that requires combining two ascending order lists into a new sorted linked list. The resulting linked list should maintain the ascending order and include all the nodes from both input lists. This problem is often encountered in algorithmic challenges and is a fundamental operation in various applications, such as merging results from different sorted data sources.

合并两个有序链表是一个常见的问题，需要将两个升序链表合并为一个新的升序链表。合并后的链表应保持升序，并包括两个输入链表中的所有节点。这个问题经常在算法挑战中遇到，是在各种应用中（如合并来自不同排序数据源的结果）的一项基本操作。

1. Problem Description

问题描述

Given two sorted linked lists, the task is to merge them into a single sorted linked list. The merged linked list should be in ascending order, and it should be formed by splicing together all the nodes from the two input lists.

给定两个排序的链表，任务是将它们合并为一个排序的链表。合并后的链表应为升序，并通过拼接两个输入链表中的所有节点来形成。

Example

示例

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Explanation: The merged list should maintain the ascending order.

输入: l1 = [1,2,4], l2 = [1,3,4]
输出: [1,1,2,3,4,4]
解释: 合并后的链表应保持升序。

Constraints

约束条件

The number of nodes in both lists is in the range [0, 50].
Both l1 and l2 are sorted in non-decreasing order.
两个链表中的节点数量都在 [0, 50] 范围内。
l1 和 l2 都按非递减顺序排序。

2. Algorithm Analysis

算法分析

To merge two sorted linked lists, we can use an iterative approach. The idea is to create a new linked list and add nodes from either l1 or l2 one by one, in ascending order, until all nodes from both lists are included in the new list.

为了合并两个有序链表，我们可以使用迭代方法。这个思路是创建一个新的链表，并按升序从 l1 或 l2 中逐个添加节点，直到将两个链表中的所有节点都包括在新链表中。

Core Idea

核心思路

Initialize a dummy node to act as the starting point for the new merged list.
Use a pointer to track the current position in the merged list.
Compare the values at the current nodes of l1 and l2:
- If the value in l1 is smaller or equal, add the l1 node to the merged list, and move l1 to the next node.
- Otherwise, add the l2 node to the merged list, and move l2 to the next node.
Continue this process until one of the lists is exhausted.
If there are remaining nodes in either l1 or l2, append them to the end of the merged list.
Return the merged list, which starts from the node following the dummy node.
初始化一个虚拟节点，作为新合并链表的起始点。
使用一个指针跟踪合并链表中的当前位置。
比较 l1 和 l2 当前节点的值：
- 如果 l1 中的值较小或相等，则将 l1 节点添加到合并链表中，并将 l1 移动到下一个节点。
- 否则，将 l2 节点添加到合并链表中，并将 l2 移动到下一个节点。
继续这个过程，直到其中一个链表耗尽。
如果 l1 或 l2 中还有剩余节点，将它们附加到合并链表的末尾。
返回合并链表，从虚拟节点之后的节点开始。

Code Implementation

代码实现

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

def mergeTwoLists(l1, l2):
    # Initialize a dummy node to start the merged list
    dummy = ListNode()
    current = dummy

    # Traverse both lists and merge them in ascending order
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    # If there are remaining nodes in l1 or l2, attach them
    if l1:
        current.next = l1
    if l2:
        current.next = l2

    # The merged list is the next of the dummy node
    return dummy.next

Detailed Explanation

详细解释

Initialization: A dummy node is created to serve as a starting point. The current pointer is used to build the new list by linking nodes from l1 and l2.
初始化：创建一个虚拟节点作为起始点。使用 current 指针通过链接 l1 和 l2 中的节点来构建新链表。
Merging Process: The while loop runs as long as both l1 and l2 have nodes remaining. During each iteration, the smaller node between l1 and l2 is appended to the merged list.
合并过程：只要 l1 和 l2 都还有节点，while 循环就会运行。在每次迭代中，将 l1 和 l2 中较小的节点附加到合并链表中。
Appending Remaining Nodes: After the loop, one of the lists might still have nodes left. These remaining nodes are directly attached to the end of the merged list.
附加剩余节点：循环结束后，其中一个链表可能还有剩余节点。这些剩余节点将直接附加到合并链表的末尾。
Return Statement: Finally, the merged list is returned, starting from the node next to the dummy node.
返回语句：最后，返回合并链表，从虚拟节点的下一个节点开始。

Time Complexity Analysis

时间复杂度分析

The time complexity of this algorithm is O(n + m), where n and m are the lengths of l1 and l2, respectively. This is because each node from both lists is processed exactly once.

该算法的时间复杂度为 O(n + m)，其中 n 和 m 分别是 l1 和 l2 的长度。这是因为两个链表中的每个节点都被处理一次。

3. Conclusion

结论

Merging two sorted linked lists into one sorted linked list is a fundamental problem that can be solved efficiently using an iterative approach. By carefully managing pointers and ensuring that all nodes are processed in order, the resulting linked list maintains the sorted order and includes all nodes from the original lists. This method is straightforward, efficient, and widely applicable in various scenarios where sorted data needs to be combined.

将两个有序链表合并为一个有序链表是一个基本问题，可以通过迭代方法高效解决。通过仔细管理指针并确保所有节点按顺序处理，合并后的链表保持了排序顺序，并包括了原始链表中的所有节点。这种方法简单、高效，适用于需要合并排序数据的各种场景。

Post Views: 52

CODEBITWAVE