707. 设计链表

Medium

题目描述

设计链表的实现。你可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-indexed 的。

在 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) 在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
void deleteAtIndex(int index) 如果索引 index 有效，则删除链表中的第 index 个节点。

示例 1：

输入
["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 库。
最多 2000 次调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex。

解题思路

这道题要求我们设计一个链表数据结构，需要实现基本的增删查操作。我们可以选择单链表或双链表，这里推荐使用单链表实现，因为它更简洁且满足题目要求。

核心设计思想：

节点结构：定义一个 ListNode 类，包含值 val 和指向下一个节点的指针 next
虚拟头节点：使用 dummy head 简化边界情况的处理，避免特殊处理头部插入/删除
维护长度：用 size 变量记录链表长度，提高索引有效性检查的效率

关键操作实现：

get操作：遍历到指定索引位置，返回节点值
addAtHead：在虚拟头节点后插入新节点
addAtTail：遍历到链表末尾插入新节点
addAtIndex：先检查索引有效性，然后遍历到指定位置插入
deleteAtIndex：找到待删除节点的前一个节点，修改指针连接

这种实现方式时间复杂度为 O(n)（主要是遍历操作），空间复杂度为 O(1)（除了存储节点本身）。虚拟头节点的使用大大简化了代码逻辑，避免了大量的边界条件判断。

代码实现

class MyLinkedList {
private:
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int x) : val(x), next(nullptr) {}
    };
    
    ListNode* head;
    int size;
    
public:
    MyLinkedList() {
        head = new ListNode(0); // dummy head
        size = 0;
    }
    
    int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode* cur = head;
        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;
        if (index < 0) index = 0;
        
        size++;
        ListNode* pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred->next;
        }
        
        ListNode* toAdd = new ListNode(val);
        toAdd->next = pred->next;
        pred->next = toAdd;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        
        size--;
        ListNode* pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred->next;
        }
        
        ListNode* toDelete = pred->next;
        pred->next = pred->next->next;
        delete toDelete;
    }
};

class MyLinkedList:

    def __init__(self):
        self.head = ListNode(0)  # dummy head
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        
        cur = self.head
        for _ in range(index + 1):
            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
        if index < 0:
            index = 0
        
        self.size += 1
        pred = self.head
        for _ in range(index):
            pred = pred.next
        
        to_add = ListNode(val)
        to_add.next = pred.next
        pred.next = to_add

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

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

public class MyLinkedList {
    
    public class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int x) {
            val = x;
            next = null;
        }
    }
    
    private ListNode head;
    private int size;

    public MyLinkedList() {
        head = new ListNode(0); // dummy head
        size = 0;
    }
    
    public int Get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode cur = head;
        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;
        
        size++;
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }
    
    public void DeleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        
        size--;
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        
        pred.next = pred.next.next;
    }
}

var MyLinkedList = function() {
    this.head = null;
    this.size = 0;
};

MyLinkedList.prototype.get = function(index) {
    if (index < 0 || index >= this.size) return -1;
    let current = this.head;
    for (let i = 0; i < index; i++) {
        current = current.next;
    }
    return current.val;
};

MyLinkedList.prototype.addAtHead = function(val) {
    const newNode = { val: val, next: this.head };
    this.head = newNode;
    this.size++;
};

MyLinkedList.prototype.addAtTail = function(val) {
    const newNode = { val: val, next: null };
    if (!this.head) {
        this.head = newNode;
    } else {
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }
    this.size++;
};

MyLinkedList.prototype.addAtIndex = function(index, val) {
    if (index > this.size) return;
    if (index <= 0) {
        this.addAtHead(val);
        return;
    }
    if (index === this.size) {
        this.addAtTail(val);
        return;
    }
    
    const newNode = { val: val, next: null };
    let current = this.head;
    for (let i = 0; i < index - 1; i++) {
        current = current.next;
    }
    newNode.next = current.next;
    current.next = newNode;
    this.size++;
};

MyLinkedList.prototype.deleteAtIndex = function(index) {
    if (index < 0 || index >= this.size) return;
    
    if (index === 0) {
        this.head = this.head.next;
    } else {
        let current = this.head;
        for (let i = 0; i < index - 1; i++) {
            current = current.next;
        }
        current.next = current.next.next;
    }
    this.size--;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
get	O(n)	O(1)
addAtHead	O(1)	O(1)
addAtTail	O(n)	O(1)
addAtIndex	O(n)	O(1)
deleteAtIndex	O(n)	O(1)
总空间复杂度	-	O(n)

说明：

时间复杂度：大部分操作需要遍历链表到指定位置，最坏情况下为 O(n)
空间复杂度：除了存储 n 个节点外，只需要常数额外空间
addAtHead 是 O(1) 因为直接在虚拟头节点后插入

题目描述#

解题思路#

解题思路#

核心设计思想：#

关键操作实现：#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

解题思路

核心设计思想：

关键操作实现：

代码实现

复杂度分析

相关题目