题目
给定两个升序链表（链表中节点存储的元素是按非递减顺序排列），其头节点分别为 head1 和 head2 。请将两个升序链表合并为一个新的 升序 链表并返回，其中新链表是通过拼接给定的两个链表的所有节点组成的。
例如：
原链表转换为列表：[1, 2, 4]、[1, 3, 4]
最终的链表转换为列表：[1, 1, 2, 3, 4, 4]原链表转换为列表：[]、[]
最终的链表转换为列表：[]原链表转换为列表：[]、[1, 3, 4]
最终的链表转换为列表：[1, 3, 4]
已知 链表节点的定义、链表与列表相互转换 的代码如下：
class ListNode: # 单链表
def __init__(self, val=0, next=None):
self.val = val # 链表节点上存储的元素
self.next = next # 指向下一个链表节点
def list_to_list_node(numbers): # 将列表转换为单向链表，并返回链表的头节点
dummy_head = ListNode(0)
pre = dummy_head
for number in numbers:
pre.next = ListNode(number)
pre = pre.next
pre = dummy_head.next
return pre
def list_node_to_list(node): # 将单向链表转换为列表
result = []
while node:
result.append(node.val)
node = node.next
return result
实现思路--迭代
- 使用
迭代的方式实现 - 设置一个虚拟头节点
dummy_head，同时让当前节点 cur = dummy_head - 当 head1 和 head2 都非空时进行 while 循环，如果 head1 大于 head2 节点下的元素，就让 cur 通过 next 指向当前元素较小的 head2 ，同时 head2 需要向后移动一位，否则需指向 head1 且 head1 需要向后移动一位
- 每次循环后 cur 需要向后移动一位，让其指向下一个节点 cur.next
- 循环结束后 head1 和 head2 最多会有1个还没有合并完，也就是说最多有一个非空，但由于两个链表都是有序链表，所以不管哪个链表非空，其剩余节点下的元素都会比前面合并链表中所有元素都要大，因此，我们只需要让 cur 通过 next 指向未合并完的链表即可
- 最后返回头节点时，需要注意新的头节点是 dummy_head 的下一个节点，即
dummy_head.next
代码实现
class Solution:
def mergeTwoLists(self, head1: ListNode, head2: ListNode) -> ListNode:
dummy_head = ListNode(0) # 设置一个虚拟头节点
cur = dummy_head
while head1 is not None and head2 is not None:
if head1.val > head2.val: # 当前节点通过 next 指向当前元素较小的链表节点
cur.next, head2 = head2, head2.next
else:
cur.next, head1 = head1, head1.next
cur = cur.next
# 合并后 head1 / head2 最多有1个还没有合并完，直接让 cur 通过 next 指向未合并完的链表
cur.next = head1 if head1 is not None else head2
return dummy_head.next
实现思路--递归
- 使用
递归的方式实现 - 当 head1 或 head2 都是非空时，需要进行递归查找下一个节点
- 递归过程中，我们每次调用函数均会找到两个链表中头节点下元素较小的一个节点，然后把该节点返回，同时再继续去找到下一个节点
- 如果 head1 或 head2 为空，那么我们直接返回非空的那一个节点即可，到此递归查找结束
代码实现
class Solution:
def mergeTwoLists(self, head1: ListNode, head2: ListNode) -> ListNode:
if head1 is None: # 如果 head1 为空，那么直接返回 head2
return head2
elif head2 is None: # 如果 head2 为空，那么直接返回 head1
return head1
elif head1.val > head2.val: # 如果 head1 大于 head2 节点下的元素，那么返回 head2 ，同时 head2 通过next指向下一个节点
head2.next = self.mergeTwoLists(head1, head2.next)
return head2
else: # 否则返回 head1 ，同时 head1 通过next指向下一个节点
head1.next = self.mergeTwoLists(head1.next, head2)
return head1
更多Python编程题，等你来挑战：Python编程题汇总（持续更新中……）
网友评论