美仑-专门做服装的网站,郑州做网站 熊掌号,宁波找网站建设企业,我想在家办个小型加工厂1. 算法思路
这段代码的核心思想是 合并两个有序链表。具体步骤如下#xff1a; 初始化哨兵节点#xff1a; 创建一个哨兵节点 dummy#xff0c;用于简化链表操作#xff0c;避免处理头节点的特殊情况。使用指针 cur 指向 dummy#xff0c;用于构建新的链表。 遍历两个链… 1. 算法思路
这段代码的核心思想是 合并两个有序链表。具体步骤如下 初始化哨兵节点 创建一个哨兵节点 dummy用于简化链表操作避免处理头节点的特殊情况。使用指针 cur 指向 dummy用于构建新的链表。 遍历两个链表 使用 while l1 and l2 循环遍历两个链表比较当前节点的值 如果 l1.val l2.val将 l1 节点连接到 cur 的后面并移动 l1 指针。否则将 l2 节点连接到 cur 的后面并移动 l2 指针。 每次连接一个节点后移动 cur 指针到新连接的节点。 处理剩余部分 当其中一个链表遍历完毕后将另一个链表的剩余部分直接连接到 cur 的后面。 返回结果 返回 dummy.next即合并后的链表的头节点。
2. 时间复杂度
最坏情况 需要遍历两个链表的全部节点假设两个链表的长度分别为 m 和 n则时间复杂度为 O(m n)。 最好情况 如果其中一个链表为空直接返回另一个链表时间复杂度为 O(1)。
3. 空间复杂度
额外空间 只使用了常数级别的额外空间哨兵节点 dummy 和指针 cur因此空间复杂度为 O(1)。 原地修改 代码直接修改了输入的链表没有创建新的链表节点因此空间复杂度较低。
class Solution:def mergeTwoLists(self, l1, l2):dummy ListNode(0) # 哨兵节点cur dummywhile l1 and l2:if l1.val l2.val:cur.next l1l1 l1.nextelse:cur.next l2l2 l2.nextcur cur.nextcur.next l1 if l1 else l2 # 将剩余部分连接到结果链表return dummy.next 原代码
class Solution(object):def mergeTwoLists(self, list1, list2)::type list1: Optional[ListNode]:type list2: Optional[ListNode]:rtype: Optional[ListNode]dummy ListNode(0)cur dummywhile list1 and list2:if list1.val list2.val:cur.next list1list1 list1.nextelse:cur.next list2list2 list2.nextcur cur.nextcur.next list1 if list1 else list2return dummy.next
