707. 设计链表

题目描述

自己实现一个链表类 MyLinkedList，可以用单向或双向链表。节点下标从 0 开始。不要使用语言内置的链表库。

MyLinkedList()：创建空链表。get(index)：返回下标为 index 的节点的值，下标无效时返回 -1。addAtHead(val)：在最前面插入值为 val 的节点，使它成为新的头节点。addAtTail(val)：在最后追加值为 val 的节点。

addAtIndex(index, val)：在下标 index 的节点前面插入值为 val 的新节点；index 恰好等于链表长度时追加到末尾；index 大于长度时不做任何事。deleteAtIndex(index)：下标有效时删除该节点，否则不做任何事。

除 get 外，其余方法都没有返回值。测试数据以方法名序列和参数序列给出，输出数组中无返回值的调用对应 null。

示例 1

输入：操作 = ["MyLinkedList","addAtHead","deleteAtIndex","addAtTail","get"]
参数 = [[],[1],[0],[2],[0]]
输出：[null,null,null,null,2]

解释：插入 1 后又删掉它，链表变空；再在末尾加入 2，下标 0 处的值为 2。

数据范围

0 <= index, val <= 1000
不要使用内置的链表库。
get、addAtHead、addAtTail、addAtIndex、deleteAtIndex 合计调用不超过 2000 次。

解题思路：单链表 + 哑节点

在真正的头节点前放一个哨兵节点 dummy，并用 size 记录长度。插入和删除都只需要找到目标位置的前一个节点 prev：从 dummy 出发走 index 步即可。插入是 prev.next = 新节点(val, prev.next)，删除是 prev.next = prev.next.next。头插、尾插分别是 index = 0 和 index = size 的特例。

为什么正确

从 dummy.next 开始恰好有 size 个节点；从 dummy 走 i 步到达的是下标 i 的前一个节点。

复杂度分析

get/addAtIndex/deleteAtIndex/addAtTail 为 O(index)，最坏 O(n)；addAtHead 为 O(1)；空间 O(n)。

易错点

没有哨兵节点时，在头部插入、删除头节点都要特判，很容易出错。addAtIndex 允许 index == size（插到末尾），而 get 和 deleteAtIndex 要求 index < size，两种边界不一样。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class MyNode:
    def __init__(self, val: int = 0, nxt=None):
        self.val = val
        self.next = nxt

class MyLinkedList:
    def __init__(self):
        self.dummy = MyNode()
        self.size = 0

    def get(self, index: int) -> int:
        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: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        prev = self.dummy
        for _ in range(index):
            prev = prev.next
        prev.next = MyNode(val, prev.next)
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        prev = self.dummy
        for _ in range(index):
            prev = prev.next
        prev.next = prev.next.next
        self.size -= 1

class MyLinkedList {
    private static class MyNode {
        int val;
        MyNode next;
        MyNode(int v, MyNode n) {
            val = v;
            next = n;
        }
    }

    private MyNode dummy;
    private int size;

    public MyLinkedList() {
        dummy = new MyNode(0, null);
        size = 0;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        MyNode 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;
        }
        MyNode prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        prev.next = new MyNode(val, prev.next);
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        MyNode prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        prev.next = prev.next.next;
        size--;
    }
}

struct MyNode {
    int val;
    MyNode* next;
    MyNode(int v = 0, MyNode* n = nullptr) : val(v), next(n) {}
};

class MyLinkedList {
public:
    MyNode* dummy;
    int size;

    MyLinkedList() {
        dummy = new MyNode();
        size = 0;
    }

    int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        MyNode* 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(size, val);
    }

    void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        MyNode* prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
        prev->next = new MyNode(val, prev->next);
        size++;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        MyNode* prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
        MyNode* del = prev->next;
        prev->next = del->next;
        delete del;
        size--;
    }
};

type MyNode struct {
	val  int
	next *MyNode
}

type MyLinkedList struct {
	dummy *MyNode
	size  int
}

func newMyNode(val int, nxt *MyNode) *MyNode {
	return &MyNode{val: val, next: nxt}
}

func Constructor() MyLinkedList {
	dummy := newMyNode(0, nil)
	return MyLinkedList{dummy: dummy, size: 0}
}

func (this *MyLinkedList) Get(index int) int {
	if index < 0 || index >= this.size {
		return -1
	}
	cur := this.dummy.next
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	return cur.val
}

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

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

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index > this.size {
		return
	}
	prev := this.dummy
	for i := 0; i < index; i++ {
		prev = prev.next
	}
	prev.next = newMyNode(val, prev.next)
	this.size++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= this.size {
		return
	}
	prev := this.dummy
	for i := 0; i < index; i++ {
		prev = prev.next
	}
	prev.next = prev.next.next
	this.size--
}

class MyNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class MyLinkedList {
    constructor() {
        this.dummy = new MyNode();
        this.size = 0;
    }

    get(index) {
        if (index < 0 || index >= this.size) {
            return -1;
        }
        let cur = this.dummy.next;
        for (let i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    addAtHead(val) {
        this.addAtIndex(0, val);
    }

    addAtTail(val) {
        this.addAtIndex(this.size, val);
    }

    addAtIndex(index, val) {
        if (index > this.size) {
            return;
        }
        let prev = this.dummy;
        for (let i = 0; i < index; i++) {
            prev = prev.next;
        }
        prev.next = new MyNode(val, prev.next);
        this.size++;
    }

    deleteAtIndex(index) {
        if (index < 0 || index >= this.size) {
            return;
        }
        let prev = this.dummy;
        for (let i = 0; i < index; i++) {
            prev = prev.next;
        }
        prev.next = prev.next.next;
        this.size--;
    }
}

class MyNode {
    val: number;
    next: MyNode | null;
    constructor(val: number = 0, next: MyNode | null = null) {
        this.val = val;
        this.next = next;
    }
}

class MyLinkedList {
    dummy: MyNode;
    size: number;

    constructor() {
        this.dummy = new MyNode();
        this.size = 0;
    }

    get(index: number): number {
        if (index < 0 || index >= this.size) {
            return -1;
        }
        let cur: MyNode = this.dummy.next!;
        for (let i = 0; i < index; i++) {
            cur = cur.next!;
        }
        return cur.val;
    }

    addAtHead(val: number): void {
        this.addAtIndex(0, val);
    }

    addAtTail(val: number): void {
        this.addAtIndex(this.size, val);
    }

    addAtIndex(index: number, val: number): void {
        if (index > this.size) {
            return;
        }
        let prev: MyNode = this.dummy;
        for (let i = 0; i < index; i++) {
            prev = prev.next!;
        }
        prev.next = new MyNode(val, prev.next);
        this.size++;
    }

    deleteAtIndex(index: number): void {
        if (index < 0 || index >= this.size) {
            return;
        }
        let prev: MyNode = this.dummy;
        for (let i = 0; i < index; i++) {
            prev = prev.next!;
        }
        prev.next = prev.next!.next;
        this.size--;
    }
}

载入编辑器，自己跑一遍 →

其他解法

单链表只能从头向后找前驱节点；双向链表可以从较近的一端出发，用更多指针换取更短的定位路径。

解法 2：双向链表 + 头尾哑节点时间 O(min(index, n − index))，空间 O(n)

每个节点同时保存 prev 和 next。头尾各放一个哑节点，插入和删除都不用特判边界。定位第 index 个节点时，若 index 靠前就从头哑节点向后走，否则从尾哑节点向前走。插入时找到原第 index 个节点，把新节点接在它前面。

定位最多走一半长度，addAtTail 是 O(1)。代价是每个节点多一个指针，插入和删除要同时维护四个指针。

class DNode:
    def __init__(self, val: int = 0):
        self.val = val
        self.prev = None
        self.next = None

class MyLinkedList:
    def __init__(self):
        self.head = DNode()
        self.tail = DNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def _node(self, index: int) -> DNode:
        if index < self.size - index:
            cur = self.head.next
            for _ in range(index):
                cur = cur.next
        else:
            cur = self.tail
            for _ in range(self.size - index):
                cur = cur.prev
        return cur

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        return self._node(index).val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        nxt = self._node(index)
        node = DNode(val)
        node.prev, node.next = nxt.prev, nxt
        nxt.prev.next = node
        nxt.prev = node
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        node = self._node(index)
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

class MyLinkedList {
    private static class DNode {
        int val;
        DNode prev, next;
        DNode(int val) { this.val = val; }
    }

    private final DNode head = new DNode(0), tail = new DNode(0);
    private int size = 0;

    public MyLinkedList() {
        head.next = tail;
        tail.prev = head;
    }

    private DNode node(int index) {
        DNode cur;
        if (index < size - index) {
            cur = head.next;
            for (int i = 0; i < index; i++) cur = cur.next;
        } else {
            cur = tail;
            for (int i = 0; i < size - index; i++) cur = cur.prev;
        }
        return cur;
    }

    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        return node(index).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;
        DNode nxt = node(index);
        DNode cur = new DNode(val);
        cur.prev = nxt.prev;
        cur.next = nxt;
        nxt.prev.next = cur;
        nxt.prev = cur;
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        DNode cur = node(index);
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
        size--;
    }
}

class MyLinkedList {
    struct DNode {
        int val;
        DNode* prev = nullptr;
        DNode* next = nullptr;
        DNode(int v) : val(v) {}
    };
    DNode* head;
    DNode* tail;
    int size = 0;

    DNode* node(int index) {
        DNode* cur;
        if (index < size - index) {
            cur = head->next;
            for (int i = 0; i < index; i++) cur = cur->next;
        } else {
            cur = tail;
            for (int i = 0; i < size - index; i++) cur = cur->prev;
        }
        return cur;
    }

public:
    MyLinkedList() {
        head = new DNode(0);
        tail = new DNode(0);
        head->next = tail;
        tail->prev = head;
    }

    int get(int index) {
        if (index < 0 || index >= size) return -1;
        return node(index)->val;
    }

    void addAtHead(int val) { addAtIndex(0, val); }

    void addAtTail(int val) { addAtIndex(size, val); }

    void addAtIndex(int index, int val) {
        if (index > size) return;
        DNode* nxt = node(index);
        DNode* cur = new DNode(val);
        cur->prev = nxt->prev;
        cur->next = nxt;
        nxt->prev->next = cur;
        nxt->prev = cur;
        size++;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        DNode* cur = node(index);
        cur->prev->next = cur->next;
        cur->next->prev = cur->prev;
        delete cur;
        size--;
    }
};

type DNode struct {
	val        int
	prev, next *DNode
}

type MyLinkedList struct {
	head, tail *DNode
	size       int
}

func Constructor() MyLinkedList {
	head, tail := &DNode{}, &DNode{}
	head.next = tail
	tail.prev = head
	return MyLinkedList{head: head, tail: tail}
}

func (this *MyLinkedList) node(index int) *DNode {
	var cur *DNode
	if index < this.size-index {
		cur = this.head.next
		for i := 0; i < index; i++ {
			cur = cur.next
		}
	} else {
		cur = this.tail
		for i := 0; i < this.size-index; i++ {
			cur = cur.prev
		}
	}
	return cur
}

func (this *MyLinkedList) Get(index int) int {
	if index < 0 || index >= this.size {
		return -1
	}
	return this.node(index).val
}

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

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

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index > this.size {
		return
	}
	nxt := this.node(index)
	cur := &DNode{val: val, prev: nxt.prev, next: nxt}
	nxt.prev.next = cur
	nxt.prev = cur
	this.size++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= this.size {
		return
	}
	cur := this.node(index)
	cur.prev.next = cur.next
	cur.next.prev = cur.prev
	this.size--
}

class DNode {
    constructor(val = 0) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

class MyLinkedList {
    constructor() {
        this.head = new DNode();
        this.tail = new DNode();
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.size = 0;
    }

    node(index) {
        let cur;
        if (index < this.size - index) {
            cur = this.head.next;
            for (let i = 0; i < index; i++) cur = cur.next;
        } else {
            cur = this.tail;
            for (let i = 0; i < this.size - index; i++) cur = cur.prev;
        }
        return cur;
    }

    get(index) {
        if (index < 0 || index >= this.size) return -1;
        return this.node(index).val;
    }

    addAtHead(val) {
        this.addAtIndex(0, val);
    }

    addAtTail(val) {
        this.addAtIndex(this.size, val);
    }

    addAtIndex(index, val) {
        if (index > this.size) return;
        const nxt = this.node(index);
        const cur = new DNode(val);
        cur.prev = nxt.prev;
        cur.next = nxt;
        nxt.prev.next = cur;
        nxt.prev = cur;
        this.size++;
    }

    deleteAtIndex(index) {
        if (index < 0 || index >= this.size) return;
        const cur = this.node(index);
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
        this.size--;
    }
}

class DNode {
    val: number;
    prev: DNode | null = null;
    next: DNode | null = null;

    constructor(val: number = 0) {
        this.val = val;
    }
}

class MyLinkedList {
    head: DNode;
    tail: DNode;
    size: number;

    constructor() {
        this.head = new DNode();
        this.tail = new DNode();
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.size = 0;
    }

    node(index: number): DNode {
        let cur: DNode;
        if (index < this.size - index) {
            cur = this.head.next!;
            for (let i = 0; i < index; i++) cur = cur.next!;
        } else {
            cur = this.tail;
            for (let i = 0; i < this.size - index; i++) cur = cur.prev!;
        }
        return cur;
    }

    get(index: number): number {
        if (index < 0 || index >= this.size) return -1;
        return this.node(index).val;
    }

    addAtHead(val: number): void {
        this.addAtIndex(0, val);
    }

    addAtTail(val: number): void {
        this.addAtIndex(this.size, val);
    }

    addAtIndex(index: number, val: number): void {
        if (index > this.size) return;
        const nxt = this.node(index);
        const cur = new DNode(val);
        cur.prev = nxt.prev;
        cur.next = nxt;
        nxt.prev!.next = cur;
        nxt.prev = cur;
        this.size++;
    }

    deleteAtIndex(index: number): void {
        if (index < 0 || index >= this.size) return;
        const cur = this.node(index);
        cur.prev!.next = cur.next;
        cur.next!.prev = cur.prev;
        this.size--;
    }
}

设计专题的其他题目

查看设计全部题目 →