LeetCode 707：设计链表（单链表 + dummy 虚拟头节点 + size）

题目

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val和next。val是当前节点的值，next是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性prev以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现MyLinkedList类：

• MyLinkedList()初始化MyLinkedList对象。
• int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。
• void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。插入完成后，新节点成为链表的第一个节点。
• void addAtTail(int val)将一个值为val的节点追加到链表末尾。
• void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index == 链表长度，则追加到末尾；如果index > 链表长度，则不插入。
• void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。

示例：

输入：

["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]]

输出：

[null, null, null, null, 2, null, 3]

解释：

• addAtHead(1)：1
• addAtTail(3)：1->3
• addAtIndex(1,2)：1->2->3
• get(1)：返回2
• deleteAtIndex(1)：1->3
• get(1)：返回3

解法选择：单链表 + dummy 虚拟头节点

这题可以用双链表，但初学时最稳、最容易写对的是：

• 单链表节点：只维护val和next
• dummy虚拟头节点：放在真实链表前面（不算下标）
• size：记录真实节点数量

这样做的最大好处是：所有插入/删除都能统一成“先找到前驱节点，再改 next”，不需要对“删除头节点 / 头部插入”写额外特判。

关键约定：dummy 不算下标

假设链表是：

dummy -> A -> B -> C -> None 0 1 2

• dummy是虚拟头节点（不算第 0 个节点）
• 下标0的节点是dummy.next（也就是 A）

因此会出现两个非常固定的走法：

• 找第 index 个节点：从 dummy 走index + 1步
• 找第 index 个节点的前驱节点：从 dummy 走index步

后面get / addAtIndex / deleteAtIndex都靠这个规则。

代码

classListNode:def__init__(self,val=0,next=None):self.val=val self.next=nextclassMyLinkedList:def__init__(self):self.size=0self.dummy=ListNode(0)# 虚拟头节点（不算下标）defget(self,index:int)->int:# 1) 下标检查：合法范围是 [0, size-1]ifindex<0orindex>=self.size:return-1# 2) 从 dummy 出发，走 index+1 步到达第 index 个真实节点cur=self.dummyfor_inrange(index+1):cur=cur.next# 3) cur 已经是目标节点returncur.valdefaddAtHead(self,val:int)->None:# 头插等价于在 index=0 处插入self.addAtIndex(0,val)defaddAtTail(self,val:int)->None:# 尾插等价于在 index=size 处插入（题目规定：index==长度表示追加）self.addAtIndex(self.size,val)defaddAtIndex(self,index:int,val:int)->None:# 1) 如果 index > size，直接不插入ifindex>self.size:return# 2) 兼容写法：index<0 当作插到头部（虽然题目保证 index>=0）ifindex<0:index=0# 3) 找到“index 位置的前驱节点”# 因为 dummy 不算下标，所以走 index 步就到前驱cur=self.dummyfor_inrange(index):cur=cur.next# 4) 插入新节点：new_node.next 指向原后继，再让前驱 cur.next 指向 new_node# 这一句等价于：# new_node = ListNode(val)# new_node.next = cur.next# cur.next = new_nodecur.next=ListNode(val,cur.next)# 5) 更新长度self.size+=1defdeleteAtIndex(self,index:int)->None:# 1) 下标检查ifindex<0orindex>=self.size:return# 2) 找到“index 位置的前驱节点”cur=self.dummyfor_inrange(index):cur=cur.next# 3) 删除：跳过目标节点（cur.next），让 cur.next 指向 cur.next.nextcur.next=cur.next.next# 4) 更新长度self.size-=1

逐函数解析（对应题目 5 个接口）

1）get(index)

• 为什么从 dummy 开始？dummy 是统一入口。
• 为什么走index+1步？因为dummy.next才是下标 0 的真实节点。
• 时间复杂度：最坏走到尾部 (O(n))

2）addAtHead(val)

• 头插就是在下标 0 前插入 → 复用addAtIndex(0, val)

3）addAtTail(val)

• 当前尾部的下标是size-1
• 题目规定index == size表示“插到末尾后面”
• 所以复用addAtIndex(size, val)

新节点的 next 是什么？

• 当index == size时，前驱会走到当前最后一个真实节点
• 当前尾节点的next原本是None
• 因此新节点会被创建成ListNode(val, None)，自然成为新尾节点

4）addAtIndex(index, val)

核心思想：先找前驱，再插入。

• 找前驱：从 dummy 走index步
• 插入：cur.next = ListNode(val, cur.next)
• 维护size

5）deleteAtIndex(index)

同样是：先找前驱，再跳过。

• 找前驱：从 dummy 走index步
• 删除：cur.next = cur.next.next
• 维护size

复杂度分析

设链表长度为 (n)：

• get：最坏遍历 (O(n))
• addAtHead：复用addAtIndex(0)，定位前驱 (O(1))，插入改指针 (O(1)) → (O(1))
• addAtTail：最坏需要走到尾部（因为没有尾指针）→ (O(n))
• addAtIndex：最坏走到 index → (O(n))
• deleteAtIndex：最坏走到 index → (O(n))
• 额外空间：只用常数指针和计数 → (O(1))（不算节点存储）

常见易错点

• dummy 是否算下标 0？不算；dummy.next才是下标 0。
• get 走几步？走index+1。
• 插入/删除找前驱走几步？走index。
• 最后是否更新 size？插入+1，删除-1。
• delete 时会不会cur.next为空？不会，因为提前检查了index < size。