LeetCode 题解工作台
设计链表
你可以选择使用单链表或者双链表，设计并实现自己的链表。 单链表中的节点应该具备两个属性： val 和 next 。 val 是当前节点的值， next 是指向下一个节点的指针/引用。 如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。 实现 My…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们创建链表虚拟头节点 `dummy`，用变量 `cnt` 记录当前链表节点个数。 具体的方法如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：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] 解释 MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3 myLinkedList.get(1); // 返回 2 myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3 myLinkedList.get(1); // 返回 3
提示：
0 <= index, val <= 1000- 请不要使用内置的 LinkedList 库。
- 调用
get、addAtHead、addAtTail、addAtIndex和deleteAtIndex的次数不超过2000。
解题思路
方法一：指针引用实现单链表
我们创建链表虚拟头节点 dummy，用变量 cnt 记录当前链表节点个数。
具体的方法如下：
get(index)：遍历链表，找到第index个节点，返回其值，如果不存在，返回 。时间复杂度 。addAtHead(val)：创建新节点，将其插入到虚拟头节点后面。时间复杂度 。addAtTail(val)：创建新节点，将其插入到链表尾部。时间复杂度 。addAtIndex(index, val)：如果index等于链表长度，则该节点将附加到链表的末尾。如果index大于链表长度，则不会插入节点。如果index小于 ，则在头部插入节点。否则，遍历链表，找到第index个节点的前一个节点，将新节点插入到该节点后面。时间复杂度 。deleteAtIndex(index)：如果索引index有效，则删除链表中的第index个节点。否则，不做任何操作。时间复杂度 。
时间复杂度见具体的方法说明。其中 为链表长度。
注意：LeetCode 平台已经内置 ListNode 单链表节点类，可以直接使用。
class MyLinkedList:
def __init__(self):
self.dummy = ListNode()
self.cnt = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.cnt:
return -1
cur = self.dummy.next
for _ in range(index):
cur = cur.next
return cur.val
def addAtHead(self, val: int) -> None:
self.addAtIndex(0, val)
def addAtTail(self, val: int) -> None:
self.addAtIndex(self.cnt, val)
def addAtIndex(self, index: int, val: int) -> None:
if index > self.cnt:
return
pre = self.dummy
for _ in range(index):
pre = pre.next
pre.next = ListNode(val, pre.next)
self.cnt += 1
def deleteAtIndex(self, index: int) -> None:
if index >= self.cnt:
return
pre = self.dummy
for _ in range(index):
pre = pre.next
t = pre.next
pre.next = t.next
t.next = None
self.cnt -= 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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on list length: O(1) for head/tail insertion if tail pointer maintained, O(n) for get or index-based insert/delete. Space complexity is O(n) for storing nodes. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Will ask about handling out-of-bound indices safely.
- question_mark
May probe your choice of singly versus doubly linked list and rationale.
- question_mark
Expect explanation of pointer updates for insertions and deletions.
常见陷阱
外企场景- error
Failing to update neighboring node pointers after insertion or deletion.
- error
Ignoring edge cases like empty list or inserting at index 0.
- error
Mismanaging tail pointer when adding at the end in singly linked list.
进阶变体
外企场景- arrow_right_alt
Implement a circular linked list with similar operations.
- arrow_right_alt
Add a method to reverse the linked list in-place using pointer swaps.
- arrow_right_alt
Implement a linked list that tracks its size and returns it in O(1).