讨论/《链表》 - 设计链表/
《链表》 - 设计链表

c++版本

一、效率

image.png

二、代码

//
// Created by 鲜榨(177421) - 86336991@qq.com on 2021/4/13.
//

/*
 * 节点定义
 */
struct Node {
    int value;
    Node *next;

    Node(int value, Node *node = nullptr) : value(value), next(node) {};
};

class MyLinkedList {

public:
    Node *head;
    Node *tail;
    int length = 0;

    MyLinkedList() : head(nullptr), tail(nullptr) {}

    /*
    * 获取第 index 个节点的值,如果链表为空或 index 无效,则返回-1
    * Created by 鲜榨(177421) - 86336991@qq.com
    */
    int get(int index) {
        if (!head) {
            return -1;
        } else {
            Node *ptr = head;
            while (index > 0) {
                if (ptr->next) {
                    ptr = ptr->next;
                } else {
                    return -1;
                }
                index--;
            }
            return ptr->value;
        }
    }

    /*
    * 将值为 value 的节点插入到链表头部
    * Created by 鲜榨(177421) - 86336991@qq.com
    */
    void addAtHead(int value) {
        Node *node = new Node(value);
        if (head) {
            node->next = head;
        }
        head = node;
        length++;
    }

    /*
    * 将值为 value 的节点插入到链表尾部
    * Created by 鲜榨(177421) - 86336991@qq.com
    */
    void addAtTail(int value) {
        Node *node = new Node(value);
        if (!head) {
            head = node;
            tail = node;
            head->next = tail;
        } else {
            Node *ptr = head;
            while (ptr->next) {
                ptr = ptr->next;
            }
            ptr->next = node;
            tail = node;
        }
        length++;
    }

    /*
    * 在第 index 之前插入一个值为 value 的节点
    * 如果 index 小于 0 ,插入到头部;
    * 如果 index 大于 length,则不插入;
    * 如果 index 等于 length,插入到尾部;
    * Created by 鲜榨(177421) - 86336991@qq.com
    */
    void addAtIndex(int index, int value) {
        if (index < 0) {
            addAtHead(value);
        } else if (index > length) {
            return;
        } else {
            //第 0 个之前就是第一个
            if (index == 0) {
                addAtHead(value);
            } else {
                Node *ptr = head;
                //第 index 之前
                while (index > 1) {
                    ptr = ptr->next;
                    index--;
                }
                Node *node = new Node(value);
                node->next = ptr->next;
                ptr->next = node;
                length++;
            }
        }
    }

    /*
    * 删除第 index 个节点
    * Created by 鲜榨(177421) - 86336991@qq.com
    */
    void deleteAtIndex(int index) {
        if (!head) {
            return;
        } else {
            if (index > length - 1) {
                return;
            }
            //待删除节点的上一个节点
            Node *prev = nullptr;
            Node *ptr = head;
            while (index > 0) {
                prev = ptr;
                ptr = ptr->next;
                index--;
            }
            //待删除节点的下一个节点
            Node *next = nullptr;
            if (ptr->next) {
                next = ptr->next;
            }
            //如果没有上一个节点,说明删除的是 head
            if (!prev) {
                head = next;
            } else {
                prev->next = next;
            }
            // delete ptr;
            // ptr = nullptr;
            length--;
        }
    }
};
展开全部 20 讨论