LeetCode 707. 设计链表

2023-03-17 HGNULB 约 7 分钟

文章信息 8 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 2-5 字节美团 vivo

题目描述

✅ 707. 设计链表

题意分析

自行实现链表，支持按下标读取、头插、尾插、指定位置插入和删除。下标从 0 开始：读取和删除必须指向已有节点；插入可以等于当前长度，表示追加到末尾，超过长度则不插入。当前题面保证传入下标非负。

解法：哨兵节点 + 单链表

核心思路

[!blue]

单链表节点只保存值和后继指针。要在某位置插入或删除节点，需要先找到它的前驱；真实头节点原本没有前驱，因此在链表前固定放一个不计入数据的哨兵 dummy。这样头部修改也变成修改某个前驱的 next，无需额外分支。

用 size 保存真实节点数，保证它始终等于从 dummy.next 可达的节点数量。读取和删除只接受 0 <= index < size，插入接受 0 <= index <= size。在遍历前检查范围，可以保证读取时目标存在、删除时前驱后面确实有节点。

get 从真实头 dummy.next 出发，走 index 步到目标；插入和删除则从 dummy 出发，走同样的步数到目标前驱。插入时先让新节点指向原后继，再让前驱指向新节点，原链表剩余部分不会丢失；删除时令前驱跳过目标，直接指向目标的后继。

成功插入后 size++，成功删除后 size--，无效操作不改变计数。头插复用位置 0 的插入，尾插复用位置 size 的插入；空链表时这两个位置重合，也能使用同一套连接规则。

解题步骤

构造一个哨兵，将其后继设为空，并令 size = 0。

读取：下标无效返回 -1；否则从真实头走到目标并返回值。

插入：下标超过长度就直接结束；否则从哨兵找到前驱，依次连接“新节点到原后继”和“前驱到新节点”，再增加长度。

删除：下标无效就直接结束；否则找到前驱，让它跳过目标，再减少长度。

头插和尾插分别调用按下标插入，统一维护连接与长度。

代码实现

// 读取定位目标节点，插入与删除定位前驱节点。
class MyLinkedList {
    private final ListNode dummy;
    private int size;

    public MyLinkedList() {
        dummy = new ListNode(0);
        size = 0;
    }

    public int get(int index) {
        // 读取或删除必须指向已有节点，不能等于长度
        if (index < 0 || index >= size) {
            return -1;
        }

        // 读取从真实头节点出发，修改才需要定位前驱
        ListNode 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;
        }

        ListNode prev = dummy;

        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        ListNode node = new ListNode(val);

        // 先接住原后继，再把新节点挂到前驱之后
        node.next = prev.next;
        prev.next = node;
        // 只有完成插入才增加真实节点数
        size++;
    }

    public void deleteAtIndex(int index) {
        // 读取或删除必须指向已有节点，不能等于长度
        if (index < 0 || index >= size) {
            return;
        }

        ListNode prev = dummy;

        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        prev.next = prev.next.next;
        // 成功摘除后同步真实节点数
        size--;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }
}

// 读取定位目标节点，插入与删除定位前驱节点。
type MyLinkedList struct {
    dummy *ListNode
    size  int
}

type ListNode struct {
    Val  int
    Next *ListNode
}

func Constructor() MyLinkedList {
    return MyLinkedList{dummy: &ListNode{Val: 0}, size: 0}
}

func (l *MyLinkedList) Get(index int) int {
    // 读取或删除必须指向已有节点，不能等于长度
    if index < 0 || index >= l.size {
        return -1
    }

    // 读取从真实头节点出发，修改才需要定位前驱
    cur := l.dummy.Next
    for i := 0; i < index; i++ {
        cur = cur.Next
    }

    return cur.Val
}

func (l *MyLinkedList) AddAtHead(val int) {
    l.AddAtIndex(0, val)
}

func (l *MyLinkedList) AddAtTail(val int) {
    l.AddAtIndex(l.size, val)
}

func (l *MyLinkedList) AddAtIndex(index int, val int) {
    // 插入允许等于长度，表示追加到末尾
    if index > l.size {
        return
    }

    prev := l.dummy
    for i := 0; i < index; i++ {
        prev = prev.Next
    }

    // 先接住原后继，再把新节点挂到前驱之后
    node := &ListNode{Val: val, Next: prev.Next}
    prev.Next = node
    // 只有完成插入才增加真实节点数
    l.size++
}

func (l *MyLinkedList) DeleteAtIndex(index int) {
    // 读取或删除必须指向已有节点，不能等于长度
    if index < 0 || index >= l.size {
        return
    }

    prev := l.dummy
    for i := 0; i < index; i++ {
        prev = prev.Next
    }

    prev.Next = prev.Next.Next
    // 成功摘除后同步真实节点数
    l.size--
}

复杂度分析

时间复杂度：头插为 $O(1)$；读取、按下标插入或删除需要寻找目标或前驱，最坏为 $O(n)$。本实现不保存尾指针，尾插也需要遍历，最坏为 $O(n)$。

空间复杂度：保存 $n$ 个真实节点占 $O(n)$，哨兵、长度和单次操作的辅助指针只占 $O(1)$。

关键点总结

[!green]

哨兵让每个真实节点都有可操作的前驱，统一头部和中间位置的修改。

读取寻找目标，修改寻找前驱，因此遍历起点不同。

size 只统计真实节点，且只在成功修改后更新。

易错点总结

[!yellow]

插入若拒绝 index == size，尾插就会失效；读取和删除却必须拒绝这个下标。

新节点尚未保存原后继，就先改前驱指针，随后可能把新节点连成自环或丢失原链表。

把哨兵算入 size，会使所有下标检查和遍历位置偏移。

无效操作也修改长度，会让计数与实际节点数不一致，影响之后的所有边界判断。

相似题目

题目	难度	关联与区别
206. 反转链表	简单	链表接口实现依赖保存后继和正确改写next，反转是验证指针操作理解的直接练习。
146. LRU 缓存	中等	把链表扩成双向结构并配合哈希定位，可支持任意节点的删除和移到头部。
补充题 202. 双向链表的节点插入	中等	都按下标定位插入位置；补充题还需同时更新前驱与后继指针。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/70476717

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！