?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