作者：冠凯雅友9 | 来源：互联网 | 2024-11-29 12:17
前言：本篇文章将探讨如何在Python中实现合并两个已排序链表的功能。我们将深入理解算法逻辑，并通过示例代码来展示其实现过程，希望能为读者提供有价值的参考。
问题描述
给定两个按照升序排列的链表，任务是将这两个链表合并成一个新的链表，新链表中的元素也应保持升序排列。
解决方案
为了高效地解决这个问题，我们可以使用一个哨兵节点（dummy node）作为新链表的起始点，然后遍历两个链表，比较当前节点的值，将较小的节点连接到新链表上，直至遍历完成所有节点。最后，如果其中一个链表还有剩余节点，则直接将其连接到新链表的末尾。
1 class Solution:
2 # 返回合并后的链表
3 def merge_sorted_lists(self, head1, head2):
4 dummy = ListNode(0)
5 current = dummy
6 while head1 and head2:
7 if head1.val 8 current.next = head1
9 head1 = head1.next
10 else:
11 current.next = head2
12 head2 = head2.next
13 current = current.next
14 if head1:
15 current.next = head1
16 elif head2:
17 current.next = head2
18 return dummy.next
上述代码中，我们首先创建了一个哨兵节点`dummy`和一个指针`current`指向这个哨兵节点。接着，我们通过循环遍历两个链表，每次选择较小的节点添加到新链表中，直到其中一个链表被完全遍历。最后，如果有剩余的节点，则直接将这些节点添加到新链表的末尾。
![python的交互模式怎么输出名文汉字[python常见问题]](https://img1.php1.cn/3cd4a/24cea/978/9f39a0b333a15215.gif)
京公网安备 11010802041100号