链表题解——合并两个有序链表【LeetCode】

 1. 算法思路

这段代码的核心思想是 合并两个有序链表。具体步骤如下：

1. 初始化哨兵节点：

   • 创建一个哨兵节点 dummy，用于简化链表操作，避免处理头节点的特殊情况。
   • 使用指针 cur 指向 dummy，用于构建新的链表。

2. 遍历两个链表：

   • 使用 while l1 and l2 循环遍历两个链表，比较当前节点的值：
     • 如果 l1.val < l2.val，将 l1 节点连接到 cur 的后面，并移动 l1 指针。
     • 否则，将 l2 节点连接到 cur 的后面，并移动 l2 指针。
   • 每次连接一个节点后，移动 cur 指针到新连接的节点。

3. 处理剩余部分：

   • 当其中一个链表遍历完毕后，将另一个链表的剩余部分直接连接到 cur 的后面。

4. 返回结果：

   • 返回 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