如何合并两个有序链表

# 1. 有序链表的定义和基本操作**

有序链表是一种线性数据结构，其中元素按照特定顺序（通常是升序或降序）排列。它由一系列节点组成，每个节点包含一个数据值和指向下一个节点的指针。

有序链表的基本操作包括：

- **插入：**将一个新元素插入链表中，保持有序性。
- **删除：**从链表中删除一个元素，保持有序性。
- **查找：**在链表中查找一个元素，返回其位置或指示元素不存在。
- **遍历：**遍历链表中的所有元素，从头到尾或从尾到头。

# 2. 合并有序链表的算法

有序链表的合并是一种常见的数据结构操作，它涉及将两个或多个有序链表合并为一个新的有序链表。合并有序链表有两种主要算法：迭代法和递归法。

### 2.1 迭代法

#### 2.1.1 算法原理

迭代法采用两个指针，分别指向两个待合并链表的头部。它从两个链表的头部开始，每次比较两个指针指向的节点的值，将较小的节点添加到新链表中，并移动相应的指针。此过程重复进行，直到两个指针都指向空。

#### 2.1.2 代码实现

def merge_iterative(head1, head2):
    dummy = ListNode(0)  # 虚拟头节点
    curr = dummy

    while head1 and head2:
        if head1.val < head2.val:
            curr.next = head1
            head1 = head1.next
        else:
            curr.next = head2
            head2 = head2.next
        curr = curr.next

    # 处理剩余节点
    if head1:
        curr.next = head1
    if head2:
        curr.next = head2

    return dummy.next

**代码逻辑分析：**

* 创建一个虚拟头节点 `dummy`，它指向新链表的头部。
* 两个指针 `head1` 和 `head2` 指向两个待合并链表的头部。
* 进入循环，比较 `head1` 和 `head2` 指向的节点的值。
* 将较小的节点添加到新链表中，并移动相应的指针。
* 重复此过程，直到两个指针都指向空。
* 处理剩余节点，将剩余的链表连接到新链表的尾部。
* 返回新链表的头部。

### 2.2 递归法

#### 2.2.1 算法原理

递归法采用分治的思想，将两个待合并链表分成较小的子链表，递归地合并子链表，再将合并后的子链表合并为一个新的链表。

#### 2.2.2 代码实现

def merge_recursive(head1, head2):
    if not head1:
        return head2
    if not head2:
        return head1

    if head1.val < head2.val:
        head1.next = merge_recursive(head1.next, head2)
        return head1
    else:
        head2.next = merge_recursive(head1, head2.next)
        return head2

**代码逻辑分析：**

* 递归基线：如果其中一个链表为空，则直接返回另一个链表。
* 比较两个链表的头部节点的值，将较小的节点作为新链表的头部。
* 将较小节点的下一个节点与另一个链表合并，并将合并后的链表连接到新链表的头部。
* 重复此过程，直到两个链表都合并完毕。
* 返回新链表的头部。

# 3. 合并有序链表的实践应用

### 3.1 数据结构的优化

#### 3.1.1 使用哨兵节点

哨兵节点是一个特殊的节点，它位于链表的开头或结尾，不包含任何数据，但它简化了链表的某些操作。在合并有序链表时，使用哨兵节点可以避免对头节点进行特殊处理，从而简化代码。

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

def merge_two_sorted_lists_with_dummy(head1, head2):
    dummy = ListNode()
    current = dummy

    while head1 and head2:
        if head1.val < head2.val:
            current.next = head1
            head1 = head1.next
        else:
            current.next = head2
            head2 = head2.next
        current = current.next

    if head1:
        current.next = head1
    if head2:
        current.next = head2

    return dummy.next

**代码逻辑分析：**

1. 创建一个哨兵节点 `dummy`，并将其 `next` 指向合并后的链表头节点。
2. 使用 `current` 指针遍历合并后的链表，并根据 `head1` 和 `head2` 节点的值大小，将较小的节点添加到 `current.next`。
3. 将 `current` 指针移动到新添加的节点。
4. 如果 `head1` 或 `head2` 还有剩余节点，则将其添加到合并后的链表。
5. 返回哨兵节点 `dummy` 的 `next` 指针，指向合并后的链表头节点。

#### 3.1.2 使用虚拟头节点

虚拟头节点与哨兵节点类似，但它位于链表的开头，不包含任何数据。使用虚拟头节点可以简化链表的插入和删除操作。

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

def merge_two_sorted_lists_with_dummy(head1, head2):
    dummy = ListNode()
    dummy.next = head1

    prev = dummy
    while head1 and head2:
        if head1.val < head2.val:
            prev.next = head1
            head1 = head1.next
        else:
            prev.next = head2
            head2 = head2.next
        prev = prev.next

    if head1:
        prev.next = head1
    if head2:
        prev.next = head2

    return dummy.next

**代码逻辑分析：**

1. 创建一个虚拟头节点 `dummy`，并将其 `next` 指向 `head1`。
2. 使用 `