全部题目来自力扣，这里只做学习的记录，内容中部分为AI生成，有不对的地方可以评论或者私信哦~~
707. 设计链表
一、算法逻辑（每一步通顺讲解思路）
🔹 1. 初始化链表结构
构造函数中引入一个哨兵节点（dummy head），它不存储实际数据，仅用于简化头部操作；
设置一个成员变量
size来记录链表当前长度，便于判断索引合法性并优化操作逻辑。
🔹 2. 获取值 get(index)
判断索引是否合法（
0 <= index < size），越界返回 -1；从头节点开始遍历
index步，定位到目标节点；返回该节点的值。
🔹 3. 在头部插入 addAtHead(val)
在
dummy_head后插入一个新节点，指向原来的头节点；更新链表长度
size += 1；插入时间复杂度为 O(1)。
🔹 4. 在尾部插入 addAtTail(val)
从
dummy_head开始一路遍历到尾节点（current.next is None）；在尾部追加新节点；
插入时间复杂度为 O(n)，因为需要遍历整个链表。
🔹 5. 任意位置插入 addAtIndex(index, val)
插入位置合法条件：
0 <= index <= size，注意==合法是因为允许尾插；遍历到第
index-1个节点，完成插入；插入时间复杂度为 O(index)，最坏为 O(n)。
🔹 6. 删除指定位置节点 deleteAtIndex(index)
删除位置合法条件：
0 <= index < size；遍历到第
index-1个节点，让它next指向index+1节点，即跳过当前节点；删除时间复杂度为 O(index)，最坏为 O(n)。
二、核心点总结
哨兵节点 + size记录 + 链式结构 + O(n)遍历插删 是这类链表题目的核心构建思路。
✅ 哨兵节点（dummy node）避免对头节点操作的特殊判断；
✅ 使用
size记录链表长度，快速判断边界合法性；✅ 所有插入、删除都通过“遍历到前一节点”来操作；
✅ 遵循单链表结构特性，无随机访问能力。
（版本一）单链表法
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self.dummy_head = ListNode()
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
current = self.dummy_head.next
for i in range(index):
current = current.next
return current.val
def addAtHead(self, val: int) -> None:
self.dummy_head.next = ListNode(val, self.dummy_head.next)
self.size += 1
def addAtTail(self, val: int) -> None:
current = self.dummy_head
while current.next:
current = current.next
current.next = ListNode(val)
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return
current = self.dummy_head
for i in range(index):
current = current.next
current.next = ListNode(val, current.next)
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
current = self.dummy_head
for i in range(index):
current = current.next
current.next = current.next.next
self.size -= 1三、时间复杂度分析（每个函数）
| 操作 | 时间复杂度 |
|---|---|
get(index) |
O(index) |
addAtHead |
O(1) |
addAtTail |
O(n) |
addAtIndex |
O(index) |
deleteAtIndex |
O(index) |
四、空间复杂度分析
所有节点是动态创建的，除了链表本身存储的数据，没有额外结构；
所以空间开销仅为链表节点本身：
空间复杂度：O(n)，其中 n 为链表中元素个数。
✅ 总结一句话
这段代码通过使用哨兵头节点 + 封装常用操作 + 控制链表长度，使得链表插入、删除操作逻辑清晰简洁，是典型的单链表构建方式。核心在于“结构辅助 + 链式操作 + 边界控制”。
补充，仅供参考：（版本二）双链表法
（版本二）双链表法
class ListNode:
def __init__(self, val=0, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
class MyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
if index < self.size // 2:
current = self.head
for i in range(index):
current = current.next
else:
current = self.tail
for i in range(self.size - index - 1):
current = current.prev
return current.val
def addAtHead(self, val: int) -> None:
new_node = ListNode(val, None, self.head)
if self.head:
self.head.prev = new_node
else:
self.tail = new_node
self.head = new_node
self.size += 1
def addAtTail(self, val: int) -> None:
new_node = ListNode(val, self.tail, None)
if self.tail:
self.tail.next = new_node
else:
self.head = new_node
self.tail = new_node
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return
if index == 0:
self.addAtHead(val)
elif index == self.size:
self.addAtTail(val)
else:
if index < self.size // 2:
current = self.head
for i in range(index - 1):
current = current.next
else:
current = self.tail
for i in range(self.size - index):
current = current.prev
new_node = ListNode(val, current, current.next)
current.next.prev = new_node
current.next = new_node
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
if index == 0:
self.head = self.head.next
if self.head:
self.head.prev = None
else:
self.tail = None
elif index == self.size - 1:
self.tail = self.tail.prev
if self.tail:
self.tail.next = None
else:
self.head = None
else:
if index < self.size // 2:
current = self.head
for i in range(index):
current = current.next
else:
current = self.tail
for i in range(self.size - index - 1):
current = current.prev
current.prev.next = current.next
current.next.prev = current.prev
self.size -= 1
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)