重庆网站建设公司那好,网站博客自媒体轻松,甘肃省和住房建设厅网站,愿意做cps的网站描述#xff1a;给定两个按非递减顺序排列的链表#xff0c;合并两个链表#xff0c;并将结果按非递减顺序排列。
例如#xff1a;
# 链表 1: 1 - 2 - 4
# 链表 2: 1 - 3 - 4合并后的链表应该是#xff1a;1 - 1 - 2 - 3 - 4 - 4
…描述给定两个按非递减顺序排列的链表合并两个链表并将结果按非递减顺序排列。
例如
# 链表 1: 1 - 2 - 4
# 链表 2: 1 - 3 - 4合并后的链表应该是1 - 1 - 2 - 3 - 4 - 4
要求
实现一个函数 merge_two_lists(l1, l2)其中 l1 和 l2 分别为两个有序链表的头结点。 函数应该返回合并后的有序链表的头结点。
实现
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextdef merge_two_lists(l1, l2):# 创建一个虚拟头结点方便操作dummy ListNode()current dummy# 遍历两个链表while l1 and l2:# 比较当前两个节点的值将较小的节点连接到新链表中if l1.val l2.val:current.next l1l1 l1.nextelse:current.next l2l2 l2.nextcurrent current.next# 处理剩余的节点if l1:current.next l1elif l2:current.next l2# 返回合并后的链表头结点return dummy.next# 测试
l1 ListNode(1, ListNode(2, ListNode(4)))
l2 ListNode(1, ListNode(3, ListNode(4)))
result merge_two_lists(l1, l2)# 打印合并后的链表值
while result:print(result.val, end - )result result.next
# 输出1 - 1 - 2 - 3 - 4 - 4这个算法使用了双指针遍历两个有序链表比较当前节点的值将较小的节点连接到新链表中。最后处理剩余的节点并返回合并后的链表头结点。
