设计链表 图解题解

这道题到底在问什么

操作

addAtHead(1)→addAtTail(3)→addAtIndex(1,2)→get(1)→deleteAtIndex(1)→get(1)

输出

链表 1→2→3；get(1)=2；删后 1→3；get(1)=3

最优解：一步一步想明白

1. 3头插、删头都会动到「第一个节点」。如果直接拿 head 操作，每次都要特判头节点。哑头 dummy 永远站在最前、永不被删，让头节点和中间节点一视同仁，代码立刻清爽。
2. 4维护一个 size 记录当前节点个数：get/delete 越界直接返回，addAtTail 其实就是 addAtIndex(size)。一个变量省掉一堆边界纠结。
3. 5dummy → null，size = 0一开始链表是空的：只有一个哑头 D，它的 next 指向 null。size = 0。下面开始一串操作。
4. 6等价 addAtIndex(0, 1)头插就是在第 0 位前插入。先让 pred 站在第 0 位的前一个，也就是哑头 D 上（走 0 步，原地不动）。
5. 7node.next = pred.next; pred.next = node造一个值为 1 的新节点：先让它的 next 接上 pred 原来的 next（这里是 null），再让 pred.next 指向它。先接后、再接前——顺序反了会断链。size 加到 1。
6. 8size = 1，所以在第 1 位前插尾插就是 addAtIndex(size)，现在 size=1，要在第 1 位前插。pred 先回到哑头 D，准备往后走到尾节点的位置。
7. 9for i in range(1): pred = pred.next要插在第 1 位前，pred 就从哑头往后走 1 步，停在节点 1 上。此刻 pred 后面是 null，正好是链表尾。
8. 10node(3) 接到 pred 之后同样的接线：新节点 3 的 next 接 pred 原来的 next（null），pred.next 再指向它。链表变成 1→3，size = 2。
9. 11要在第 1 位前插入 2现在要在第 1 位前插一个 2，也就是塞进 1 和 3 中间。老规矩，pred 先站回哑头 D。
10. 12for i in range(1): pred = pred.next往后走 1 步，pred 停在节点 1。新节点要插在 pred 和 pred 后面那个节点（3）之间。
11. 13node.next = pred.next(=3); pred.next = node关键的中间接线：新节点 2 先把 next 接到 pred 原来的下一个（节点 3），pred.next 再改指向 2。于是 1→2→3 接通，谁都没丢。size = 3。
12. 141 → 2 → 3，size = 3三次插入后，链表是 1→2→3。注意哑头 D 始终不动，它的 next 才是真正的头。接下来查一个值。
13. 15cur = dummy.next（第 0 个）get 不用哑头当起点，直接从第 0 个真节点开始数。cur 先指向节点 1（下标 0）。
14. 16for i in range(1): cur = cur.next要第 1 个，就让 cur 往后走 1 步，停在下标 1 的节点上。
15. 17return cur.val = 2cur 现在指着的节点值就是答案：get(1) = 2。如果 index 越界（<0 或 ≥size），直接返回 -1，连走都不走。
16. 18要删第 1 个节点(值 2)删除第 1 个节点，依然是先找它的前一个。pred 站回哑头 D。
17. 19for i in range(1): pred = pred.nextpred 往后走 1 步停在节点 1。pred 后面紧跟的节点 2，就是要删掉的那个。
18. 20pred.next 指向 2把要删的节点 2 标红。删除的本质就是：让 pred 直接绕过它，指向它的下一个。
19. 21pred.next = pred.next.next关键一行：pred.next = pred.next.next，让节点 1 直接指向节点 3，节点 2 被整个绕过，从链表里消失。size 减到 2。
20. 22cur = dummy.next（下标 0）删完再 get(1)：和上次一样，cur 先回到第 0 个真节点（现在是节点 1）。
21. 23for i in range(1): cur = cur.next往后走 1 步。删掉 2 之后，下标 1 的位置已经换成了节点 3。
22. 24return cur.val = 3删除后链表是 1→3，所以 get(1) = 3。整串操作演完：五种方法，靠的全是「找前驱 + 改指针」这一套。
23. 27一句话记牢：无论增还是删，先把 pred 停到目标位置的前一个，插入是「新节点先接后、再接前」，删除是「pred 跳过下一个」。
24. 29若先做 pred.next = node假设要在 1 后插新节点。如果先把 pred.next 改指向新节点，pred 原来通往 3 的那根线就被覆盖、再也找不回 3（变成游离节点）。所以必须新节点先 next=pred.next，把 3 接住，再让 pred 指向新节点。
25. 37把链表的指针接线练熟，去 链表专题 连刷同类题；卡住时可以随时在页面里提问「这根指针为什么这么接」，比硬背更扎实。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class MyLinkedList:
    def __init__(self):
        self.dummy = Node(0)
        self.size = 0
    def get(self, index):
        if index < 0 or index >= self.size:
            return -1
        cur = self.dummy.next
        for _ in range(index):
            cur = cur.next
        return cur.val
    def addAtHead(self, val):
        self.addAtIndex(0, val)
    def addAtTail(self, val):
        self.addAtIndex(self.size, val)
    def addAtIndex(self, index, val):
        if index > self.size:
            return
        if index < 0:
            index = 0
        pred = self.dummy
        for _ in range(index):
            pred = pred.next
        node = Node(val)
        node.next = pred.next
        pred.next = node
        self.size += 1
    def deleteAtIndex(self, index):
        if index < 0 or index >= self.size:
            return
        pred = self.dummy
        for _ in range(index):
            pred = pred.next
        pred.next = pred.next.next
        self.size -= 1

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};
class MyLinkedList {
    Node* dummy;
    int sz;
public:
    MyLinkedList() : dummy(new Node(0)), sz(0) {}
    int get(int index) {
        if (index < 0 || index >= sz) return -1;
        Node* cur = dummy->next;
        for (int i = 0; i < index; i++) cur = cur->next;
        return cur->val;
    }
    void addAtHead(int val) { addAtIndex(0, val); }
    void addAtTail(int val) { addAtIndex(sz, val); }
    void addAtIndex(int index, int val) {
        if (index > sz) return;
        if (index < 0) index = 0;
        Node* pred = dummy;
        for (int i = 0; i < index; i++) pred = pred->next;
        Node* node = new Node(val);
        node->next = pred->next;
        pred->next = node;
        sz++;
    }
    void deleteAtIndex(int index) {
        if (index < 0 || index >= sz) return;
        Node* pred = dummy;
        for (int i = 0; i < index; i++) pred = pred->next;
        Node* del = pred->next;
        pred->next = del->next;
        delete del;
        sz--;
    }
};

class MyLinkedList {
    private static class Node {
        int val;
        Node next;
        Node(int v) { val = v; }
    }
    private Node dummy;
    private int size;
    public MyLinkedList() {
        dummy = new Node(0);
        size = 0;
    }
    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node cur = dummy.next;
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur.val;
    }
    public void addAtHead(int val) { addAtIndex(0, val); }
    public void addAtTail(int val) { addAtIndex(size, val); }
    public void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;
        Node pred = dummy;
        for (int i = 0; i < index; i++) pred = pred.next;
        Node node = new Node(val);
        node.next = pred.next;
        pred.next = node;
        size++;
    }
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node pred = dummy;
        for (int i = 0; i < index; i++) pred = pred.next;
        pred.next = pred.next.next;
        size--;
    }
}

# 万能起手:哑头 dummy + size
self.dummy = Node(0); self.size = 0
# 走到第 index 位的前驱 pred
pred = self.dummy
for _ in range(index): pred = pred.next
# 插入:新节点先认下家,pred 再认它
node.next = pred.next; pred.next = node  # 顺序别反
# 删除:pred 跳过下一个
pred.next = pred.next.next

// 万能起手:哑头 dummy + size
dummy = new Node(0); sz = 0;
// 走到第 index 位的前驱 pred
Node* pred = dummy;
for (int i=0;i<index;i++) pred = pred->next;
// 插入:新节点先认下家,pred 再认它
node->next = pred->next; pred->next = node;
// 删除:pred 跳过下一个
pred->next = pred->next->next;

// 万能起手:哑头 dummy + size
dummy = new Node(0); size = 0;
// 走到第 index 位的前驱 pred
Node pred = dummy;
for (int i=0;i<index;i++) pred = pred.next;
// 插入:新节点先认下家,pred 再认它
node.next = pred.next; pred.next = node;
// 删除:pred 跳过下一个
pred.next = pred.next.next;

复杂度

面试官可能追问