21.合并两个有序链表

**合并两个有序链表**

在计算机科学中，链表是一种常见的数据结构，它通过指针连接多个节点。有序链表是指每个节点都有一个值，并且这些值按照某种顺序排列。合并两个有序链表是一个经典的问题，要求我们将两个有序链表合并成一个新的有序链表。

**问题描述**

假设我们有两个有序链表：`head1` 和 `head2`。每个链表的节点都有一个值，并且这些值按照某种顺序排列。我们的任务是将这两个链表合并成一个新的有序链表，称为 `merged_list`。

**解决方案**

我们可以使用以下步骤来解决这个问题：

1. **创建一个新节点**：首先，我们需要创建一个新节点，这个节点将成为合并后的链表的头结点。
2. **比较两个链表**：然后，我们需要比较 `head1` 和 `head2` 的值。如果 `head1` 的值小于 `head2` 的值，则我们取 `head1` 作为当前链表的头结点，否则我们取 `head2`。
3. **合并链表**：接下来，我们需要将两个链表合并起来。我们可以通过递归地比较每个链表的下一个节点来实现这一点。如果 `head1` 的值小于 `head2` 的值，则我们将 `head1` 的下一个节点添加到当前链表中，否则我们将 `head2` 的下一个节点添加到当前链表中。
4. **返回合并后的链表**：最后，我们需要返回合并后的链表。

**代码示例**

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef mergeTwoLists(head1, head2):
 # 创建一个新节点作为头结点 merged_list = ListNode(0)
 current_node = merged_list # 比较两个链表并合并它们 while head1 and head2:
 if head1.val < head2.val:
 current_node.next = head1 head1 = head1.next else:
 current_node.next = head2 head2 = head2.next # 移动到下一个节点 current_node = current_node.next # 如果有剩余的链表，添加它们 if head1:
 current_node.next = head1 elif head2:
 current_node.next = head2 return merged_list.next# 测试代码head1 = ListNode(1)
head1.next = ListNode(3)
head1.next.next = ListNode(5)

head2 = ListNode(2)
head2.next = ListNode(4)
head2.next.next = ListNode(6)

merged_head = mergeTwoLists(head1, head2)

# 打印合并后的链表while merged_head:
 print(merged_head.val, end=" ")
 merged_head = merged_head.next