Leetcode: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

解题思路

定义私有成员变量
- 定义dummyHead作为链表的虚拟头节点，其next域指向实际的头节点head
- 定义size变量用于记录链表的实际元素个数
定义链表节点结构体
- 链表由节点构成，节点由数值（val）和后驱指针（next）构成
- 本题涉及到添加指定数值元素的操作，需要定义带参构造函数LinkedNode(int val)
链表初始化
- 创建虚拟头节点dummyHead，用于指向链表中第一个元素位置（即实际表头head的位置）
- 定义链表元素大小变量size，初始化为0（即当前链表中共存在0个元素）
获取指定位置元素值
- 对输入的位置进行非法判定，若小于0️⃣ 或超过数组指定大小size 则直接返回-1
- 定义链表遍历指针current，初始化为dummyHead->next
- 利用while循环不断向后寻找，current指针不断后移，直到第 index 个位置
- 返回current->val（即指定位置元素值）
表头插入元素
- 使用有参构造函数创建新节点newNode，节点值为传入的 val 变量值
- 将新节点的 next 指针指向虚拟头节点的 next 指针指向的位置，即newNode->next = dummyHead->next
- 将虚拟头节点的 next 指针指向新节点，即dummyHead->next = newNode，新节点成为实际上的链表头节点元素
- 链表元素大小增大一个
表尾插入元素
- 定义链表遍历指针current，初始化为dummyHead
- 使用有参构造函数创建新节点newNode，节点值为传入的 val 变量值
- 利用while循环不断向后寻找，current指针不断后移，直到current指向链表的最后一个元素，此时current->next == NULL
- 在当前最后一个元素后插入新节点，新节点成为新的最后一个元素节点，即current->next = newNode;
指定位置插入元素
- 对输入的位置进行非法判定
  - 若超过数组指定大小size 则直接返回（非法操作不执行）
  - 若小于0️⃣则统一重置为0️⃣，与在表头插入元素一致
- 使用有参构造函数创建新节点newNode，节点值为传入的 val 变量值
- 定义链表遍历指针current，初始化为dummyHead
- 利用while循环不断向后寻找，current指针不断后移，直到第 index 个位置
- 将新节点的 next 指针指向当前元素位置的 next 指针指向的位置，即newNode->next = current->next
- 将当前元素的next指针指向新节点，即current->next = newNode
- 链表元素大小增大一个
删除指定位置的元素
- 对输入的位置进行非法判定，若小于0️⃣ 或超过数组指定大小size 则直接返回（非法操作不执行）
- 利用while循环不断向后寻找，current指针不断后移，直到第 index 个位置
- 使用temp临时指针记录待删除节点的位置，即temp = current->next
- 重新连接链表，即current->next = current->next->next
- 释放待删除节点的内存，即delete temp;
- 加上temp=nullptr,使得temp不会成为野指针，保证内存安全
- 链表元素大小减小一个

我的答案

class MyLinkedList {
public:

    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    MyLinkedList() {
        dummyHead = new LinkedNode(0);
        size = 0;
    }
    
    int get(int index) {
        if(index < 0 || index > (size - 1)) return -1;
        LinkedNode* current = dummyHead->next;
        while(index--) {
            current = current->next;
        }
        return current->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        size++;
    }
    
    void addAtTail(int val) {
        LinkedNode* current = dummyHead;
        LinkedNode* newNode = new LinkedNode(val);
        while(current->next) {
            current = current->next;
        }
        current->next = newNode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > size) return;
        if(index < 0) index = 0;
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* current = dummyHead;
        while(index--) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index >= size) return;
        LinkedNode* current = dummyHead;
        while(index--) {
            current = current->next;
        }
        LinkedNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
        temp = nullptr;
        size--;
    }
private:
    int size;
    LinkedNode* dummyHead;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

Can

Can

Leetcode:707.设计链表

题目描述

题目示例

解题思路

我的答案

提交结果

赞助

分享