707_设计链表

【问题描述】

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：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 。

【算法设计思想】

• 1.创建链表 (myLinkedListCreate):

​ • 分配内存为链表实例并初始化头指针为 NULL，大小为 0。

​ • 2.获取元素值 (myLinkedListGet):

​ • 检查索引是否有效（范围内）。

​ • 遍历链表到达指定索引，并返回该节点的值。

​ • 3.添加节点到头部 (myLinkedListAddAtHead):

​ • 创建新节点，设置其值并将其 next 指针指向当前的头节点。

​ • 更新头指针为新节点，并增加链表大小。

​ • 4.添加节点到尾部 (myLinkedListAddAtTail):

​ • 创建新节点，设置其值并将 next 指向 NULL（表示尾部）。

​ • 如果链表为空，则新节点成为头节点。

​ • 否则，遍历到链表末尾，将最后一个节点的 next 指向新节点。

​ • 5.在指定索引插入节点 (myLinkedListAddAtIndex):

​ • 检查索引是否有效。如果索引小于等于 0，调用 addAtHead。

​ • 创建新节点，遍历到达指定索引前一个节点。

​ • 更新前一个节点的 next 指向新节点，设置新节点的 next 为当前节点的 next。

​ • 6.删除指定索引的节点 (myLinkedListDeleteAtIndex):

​ • 检查索引是否有效。如果删除头节点，则更新头指针为下一个节点。

​ • 否则，遍历到达指定索引前一个节点，保存要删除的节点并更新前一个节点的 next 指向要删除节点的下一个节点。

​ • 释放被删除节点的内存。

​ • 7.释放链表内存 (myLinkedListFree):

​ • 从头节点开始遍历整个链表，释放每个节点的内存。

​ • 最后释放链表结构体本身的内存。

【算法描述】

C:

// 定义链表节点结构体
typedef struct Node {
    int val; // 节点存储的值
    struct Node* next; // 指向下一个节点的指针
} Node;

// 定义链表结构体
typedef struct {
    Node* head; // 链表头指针
    int size; // 链表中节点的数量
} MyLinkedList;

// 创建一个新的链表实例
MyLinkedList* myLinkedListCreate() {
    MyLinkedList* obj = (MyLinkedList*)malloc(sizeof(MyLinkedList)); // 分配内存
    obj->head = NULL; // 初始化头指针为NULL
    obj->size = 0; // 初始化大小为0
    return obj; // 返回新创建的链表实例
}

// 获取链表中指定索引处的元素值
int myLinkedListGet(MyLinkedList* obj, int index) {
    if (index < 0 || index >= obj->size) { // 检查索引是否有效
        return -1; // 如果索引无效，返回-1
    }
    Node* current = obj->head; // 从头开始遍历
    for (int i = 0; i < index; i++) { // 移动到指定索引位置
        current = current->next;
    }
    return current->val; // 返回该位置节点的值
}

// 在链表头部添加一个新元素
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    newNode->val = val; // 设置新节点的值
    newNode->next = obj->head; // 新节点指向当前头节点
    obj->head = newNode; // 更新头指针为新节点
    obj->size++; // 增加链表大小
}

// 在链表尾部添加一个新元素
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    newNode->val = val; // 设置新节点的值
    newNode->next = NULL; // 尾部节点的next应为NULL

    if (obj->size == 0) { // 如果链表为空
        obj->head = newNode; // 新节点成为头节点
    } else {
        Node* current = obj->head; // 从头开始遍历
        while (current->next != NULL) { // 找到最后一个节点
            current = current->next;
        }
        current->next = newNode; // 最后一个节点的next指向新节点
    }
    obj->size++; // 增加链表大小
}

// 在指定索引处插入一个新元素
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    if (index > obj->size) { // 如果索引超出链表长度，不做任何操作
        return;
    }

    if (index <= 0) { // 如果索引小于等于0，在头部插入
        myLinkedListAddAtHead(obj, val);
        return;
    }

    Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    newNode->val = val; // 设置新节点的值

    Node* current = obj->head; // 从头开始遍历
    for (int i = 0; i < index - 1; i++) { // 移动到指定索引前一个位置
        current = current->next;
    }
    newNode->next = current->next; // 新节点的next指向当前节点的next
    current->next = newNode; // 当前节点的next指向新节点
    obj->size++; // 增加链表大小
}

// 删除指定索引处的元素
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    if (index < 0 || index >= obj->size) { // 检查索引是否有效
        return;
    }
    if (index == 0) { // 如果删除的是头节点
        Node* temp = obj->head; // 保存头节点
        obj->head = obj->head->next; // 更新头指针为下一个节点
        free(temp); // 释放旧头节点的内存
    } else {
        Node* current = obj->head; // 从头开始遍历
        for (int i = 0; i < index - 1; i++) { // 移动到指定索引前一个位置
            current = current->next;
        }
        Node* temp = current->next; // 保存要删除的节点
        current->next = temp->next; // 跳过要删除的节点
        free(temp); // 释放该节点的内存
    }
    obj->size--; // 减少链表大小
}

// 释放链表占用的所有内存
void myLinkedListFree(MyLinkedList* obj) {
    Node* current = obj->head; // 从头开始
    while (current != NULL) { // 遍历整个链表
        Node* temp = current; // 保存当前节点
        current = current->next; // 移动到下一个节点
        free(temp); // 释放当前节点的内存
    }
    free(obj); // 释放链表结构体本身的内存
}

C++：

class MyLinkedList {
public:
    // 定义链表节点的结构
    typedef struct Node {
        int val;  // 节点的值
        Node* next;  // 指向下一个节点的指针

        // 构造函数，初始化节点的值和指针
        Node(int val) {
            this->val = val;
            this->next = nullptr;
        }
    } Node;

    // 构造函数，初始化链表
    MyLinkedList() {
        dummy = new Node(0);  // 初始化一个虚拟头节点
        size = 0;  // 初始化链表大小为0
    }

    // 获取链表中第index个节点的值，如果索引无效则返回-1
    int get(int index) {
        if (index > size - 1 || index < 0) {  // 边界检查，索引范围超出时返回-1
            return -1;
        }
        Node* current = dummy->next;  // 从链表第一个有效节点开始遍历
        for (int i = 0; i < index; i++) {  // 遍历直到第index个节点
            current = current->next;
        }
        return current->val;  // 返回第index个节点的值
    }

    // 在链表头部添加一个值为val的节点
    void addAtHead(int val) {
        Node* newNode = new Node(val);  // 创建新节点
        newNode->next = dummy->next;  // 新节点的next指向当前链表的第一个节点
        dummy->next = newNode;  // 虚拟头节点的next指向新节点
        size++;  // 链表大小加1
    }

    // 在链表尾部添加一个值为val的节点
    void addAtTail(int val) {
        Node* newNode = new Node(val);  // 创建新节点
        Node* current = dummy;  // 从虚拟头节点开始遍历
        while (current->next != nullptr) {  // 遍历到链表的最后一个节点
            current = current->next;
        }
        current->next = newNode;  // 将最后一个节点的next指向新节点
        size++;  // 链表大小加1
    }

    // 在链表的第index个位置插入一个值为val的节点
    void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {  // 检查插入的索引是否合法
            return;  // 如果不合法，则不进行插入操作
        }
        if (index == 0) {  // 如果在链表头部插入
            Node* newNode = new Node(val);  // 创建新节点
            newNode->next = dummy->next;  // 新节点的next指向当前链表的第一个节点
            dummy->next = newNode;  // 虚拟头节点的next指向新节点
            size++;  // 链表大小加1
            return;  // 提前返回
        }
        Node* newNode = new Node(val);  // 创建新节点
        Node* current = dummy;  // 从虚拟头节点开始遍历
        for (int i = 0; i < index; i++) {  // 遍历直到index之前的位置
            current = current->next;
        }
        newNode->next = current->next;  // 新节点的next指向当前节点的下一个节点
        current->next = newNode;  // 当前节点的next指向新节点
        size++;  // 链表大小加1
    }

    // 删除链表中第index个节点
    void deleteAtIndex(int index) {
        if (index < 0 || index > size - 1) {  // 检查删除的索引是否合法
            return;  // 如果不合法，则不进行删除操作
        }
        Node* current = dummy;  // 从虚拟头节点开始遍历
        for (int i = 0; i < index; i++) {  // 遍历到要删除的节点之前的位置
            current = current->next;
        }
        Node* toDelete = current->next;  // 记录要删除的节点
        current->next = toDelete->next;  // 将当前节点的next指向要删除节点的下一个节点
        delete toDelete;  // 删除节点
        size--;  // 链表大小减1
    }

private:
    int size;  // 记录链表的长度
    Node* dummy;  // 虚拟头节点，方便操作
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);  // 获取链表中第index个节点的值
 * obj->addAtHead(val);  // 在链表头部插入一个节点
 * obj->addAtTail(val);  // 在链表尾部插入一个节点
 * obj->addAtIndex(index,val);  // 在第index个位置插入一个节点
 * obj->deleteAtIndex(index);  // 删除第index个节点
 */

Java：

// 节点类，表示链表中的一个节点
class Node {
    public int val;     // 节点存储的值
    public Node next;   // 指向下一个节点的指针

    // 构造函数，初始化节点的值和 next 指针
    Node(int val) {
        this.val = val;
        this.next = null; // 默认情况下，next 指针为 null
    }
}

// 单链表类，支持基本的链表操作
class MyLinkedList {
    private int size;   // 链表中的元素数量
    private Node dummy; // 虚拟头节点，方便进行链表操作

    // 构造函数，初始化链表
    public MyLinkedList() {
        dummy = new Node(0); // 初始化虚拟头节点
        size = 0;            // 初始链表为空
    }
    
    // 获取链表中第 index 个节点的值，若 index 无效则返回 -1
    public int get(int index) {
        if (index < 0 || index > size - 1) {
            return -1;  // 如果 index 超出范围，返回 -1
        }
        Node current = dummy.next; // 从虚拟头节点的下一个节点开始遍历
        for (int i = 0; i < index; i++) {
            current = current.next; // 移动到下一个节点
        }
        return current.val; // 返回目标节点的值
    }
    
    // 在链表的头部插入一个值为 val 的节点
    public void addAtHead(int val) {
        Node newNode = new Node(val);   // 创建新节点
        newNode.next = dummy.next;      // 新节点的 next 指向原头节点
        dummy.next = newNode;           // 虚拟头节点的 next 指向新节点
        size++;                         // 链表大小加 1
    }
    
    // 在链表的尾部插入一个值为 val 的节点
    public void addAtTail(int val) {
        Node current = dummy;           // 从虚拟头节点开始遍历
        while (current.next != null) {
            current = current.next;     // 找到链表的最后一个节点
        }
        Node newNode = new Node(val);   // 创建新节点
        current.next = newNode;         // 将最后一个节点的 next 指向新节点
        size++;                         // 链表大小加 1
    }
    
    // 在链表中的第 index 个节点之前插入值为 val 的节点
    // 如果 index 等于链表的长度，则该节点将附加到链表末尾
    // 如果 index 大于链表长度，则不会插入节点
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            return; // 如果 index 无效，直接返回
        }
        if (index == 0) {
            addAtHead(val);  // 如果在头部插入，直接调用 addAtHead 方法
            return;
        }
        Node newNode = new Node(val);  // 创建新节点
        Node current = dummy;          // 从虚拟头节点开始遍历
        for (int i = 0; i < index; i++) {
            current = current.next;    // 找到第 index-1 个节点
        }
        newNode.next = current.next;   // 新节点的 next 指向第 index 个节点
        current.next = newNode;        // 第 index-1 个节点的 next 指向新节点
        size++;                        // 链表大小加 1
    }
    
    // 删除链表中第 index 个节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index > size - 1) {
            return; // 如果 index 无效，直接返回
        }
        Node current = dummy;           // 从虚拟头节点开始遍历
        for (int i = 0; i < index; i++) {
            current = current.next;     // 找到第 index-1 个节点
        }
        Node toDelete = current.next;   // 找到第 index 个节点
        current.next = toDelete.next;   // 将第 index-1 个节点的 next 指向第 index+1 个节点
        toDelete = null;                // 将第 index 个节点置为 null（可选）
        size--;                         // 链表大小减 1
    }

}

/**
 * 示例用法：
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index, val);
 * obj.deleteAtIndex(index);
 */

Python：

class Node:
    def __init__(self, val=0, next=None):
        self.val = val  # 节点的值
        self.next = next  # 指向下一个节点的指针

class MyLinkedList:

    def __init__(self):
        self.dummy = Node()  # 创建一个虚拟头节点，方便操作
        self.size = 0  # 初始化链表的大小为 0

    def get(self, index: int) -> int:
        # 如果索引无效，返回 -1
        if index < 0 or index >= self.size:  # 使用 >= 进行边界检查
            return -1
        current = self.dummy.next  # 从虚拟头节点的下一个节点开始
        for i in range(index):  # 遍历到目标索引
            current = current.next
        return current.val  # 返回目标节点的值

    def addAtHead(self, val: int) -> None:
        # 在链表头部添加新节点
        newNode = Node(val)  # 创建新节点
        newNode.next = self.dummy.next  # 新节点的 next 指向当前头节点
        self.dummy.next = newNode  # 虚拟头节点的 next 指向新节点
        self.size += 1  # 链表大小加 1

    def addAtTail(self, val: int) -> None:
        # 在链表尾部添加新节点
        current = self.dummy  # 从虚拟头节点开始
        while current.next is not None:  # 遍历到链表的末尾
            current = current.next
        newNode = Node(val)  # 创建新节点
        current.next = newNode  # 将新节点添加到链表尾部
        self.size += 1  # 链表大小加 1

    def addAtIndex(self, index: int, val: int) -> None:
        # 在指定索引处添加新节点
        if index < 0 or index > self.size:  # 检查索引是否有效
            return
        if index == 0:  # 如果在头部插入
            self.addAtHead(val)  # 调用 addAtHead 方法
            return
        current = self.dummy  # 从虚拟头节点开始
        for i in range(index):  # 遍历到 index-1 个节点
            current = current.next
        newNode = Node(val)  # 创建新节点
        newNode.next = current.next  # 新节点的 next 指向第 index 个节点
        current.next = newNode  # 将第 index-1 个节点的 next 指向新节点
        self.size += 1  # 链表大小加 1

    def deleteAtIndex(self, index: int) -> None:
        # 删除指定索引处的节点
        if index < 0 or index >= self.size:  # 检查索引是否有效
            return
        current = self.dummy  # 从虚拟头节点开始
        for i in range(index):  # 遍历到 index-1 个节点
            current = current.next
        toDelete = current.next  # 找到第 index 个节点
        current.next = toDelete.next  # 删除该节点
        del toDelete  # Python 会自动处理内存，不需要显式删除
        self.size -= 1  # 链表大小减 1

# 使用示例
# obj = MyLinkedList()  # 创建一个新的链表对象
# param_1 = obj.get(index)  # 获取指定索引处的节点值
# obj.addAtHead(val)  # 在链表头部添加新值
# obj.addAtTail(val)  # 在链表尾部添加新值
# obj.addAtIndex(index, val)  # 在指定索引处添加新值
# obj.deleteAtIndex(index)  # 删除指定索引处的节点