707.设计链表

链接：707.设计链表
难度：Medium
标签：设计、链表
简介：设计链表的实现。

题解 1 - cpp

• 编辑时间：2022-09-23
• 执行用时：36ms
• 内存消耗：19.2MB
• 编程语言：cpp
• 解法介绍：构造链表。

class Node {
public:
    Node *next;
    int val;
    Node(int val): Node(val, nullptr) {}
    Node(int val, Node *next): val(val), next(next) {}
};
class MyLinkedList {
public:
    int size;
    Node *head, *tail;
    MyLinkedList(): head(nullptr), tail(nullptr), size(0) {}
    int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node *p = head;
        while (index--) p = p->next;
        return p->val;
    }
    void addAtHead(int val) {
        if (size == 0) return addFirst(val);
        head = new Node(val, head);
        size++;
    }
    void addAtTail(int val) {
        if (size == 0) return addFirst(val);
        Node *node = new Node(val);
        tail->next = node;
        tail = node;
        size++;
    }
    void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        if (index == 0) return addAtHead(val);
        if (index == size) return addAtTail(val);
        Node *p = head;
        while (--index) p = p->next;
        Node *node = new Node(val, p->next);
        p->next = node;
        size++;
    }
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        if (size == 1) {
            delete head;
            head = tail = nullptr;
        } else if (index == 0) {
            Node *node = head;
            head = head->next;
            delete node;
        } else {
            bool isTail = index == size - 1;
            Node *p = head;
            while (--index) p = p->next;
            Node *node = p->next;
            p->next = node->next;
            if (isTail) tail = p;
            delete node;
        }
        size--;
    }
    void addFirst(int val){
        head = tail = new Node(val);
        size++;
    }
};