[Vssue]0707.设计链表.md

[youngyangyang04]

https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

[Du1in9]

大佬，想问一下这题的题目你是不是抄错了呀： 题意：实现 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 大于链表的长度，则该节点将不会插入到链表中
  • 如果 index 小于0，则在头部插入节点
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

代码注释：

// head 无索引, 后移 index+1 次到目标节点
for (int i = 0; i <= index; i++) {  
    currentNode = currentNode.next;
}
// head 无索引, 后移 index 次到目标节点的上一个节点
for (int i = 0; i < index; i++) {   
    pred = pred.next;
}

[blacby]

这题第一次写，真写出来啦，哈哈，感觉算中等难度里比较简单的了

[Ding-Jiaxiong]

打卡

    //单链表写法
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }
    }

    class MyLinkedList {

        int size;  // 存储链表元素个数
        ListNode dummy;  // 虚拟头结点

        public MyLinkedList() {
            size = 0;
            dummy = new ListNode();
        }

        // 获取第 index 个节点的数值
        public int get(int index) {
            if (index < 0 || index >= size) {
                return -1;
            }

            ListNode cur = dummy;

            for (int i = 0; i <= index; i++) {
                cur = cur.next;
            }

            return cur.val;
        }

        // 在链表最前面插入一个节点
        public void addAtHead(int val) {
            ListNode newNode = new ListNode(val);
            newNode.next = dummy.next;
            dummy.next = newNode;

            size++;
        }

        // 在链表尾部插入一个节点
        public void addAtTail(int val) {
            ListNode newNode = new ListNode(val);
            ListNode cur = dummy;

            while (cur.next != null) {
                cur = cur.next;
            }

            cur.next = newNode;
            size++;
        }

        // 在指定 index 插入新节点
        public void addAtIndex(int index, int val) {

            if (index > size) return;

            if (index < 0) index = 0;

            size++;

            ListNode pre = dummy;
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }

            ListNode toAdd = new ListNode(val);
            toAdd.next = pre.next;
            pre.next = toAdd;
        }

        // 删除 index 节点
        public void deleteAtIndex(int index) {

            if (index < 0 || index >= size) return;

            size--;

            ListNode pre = dummy;

            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }

            pre.next = pre.next.next;
        }
    }

[AlvisWSY]

get 方法似乎有些问题，力扣里有的例子会导致current变成none，需要加上检测： if current == None: return -1 return current.val 就可以了

[Bryan-CR7]

打卡：注意指针不能越界访问

[xiaos2021]

打卡。自建了一个 moveCur(int index) 函数，用于移动cur指针，get，add，delete三个功能都用了这个函数，这样一下子省了很多代码量。

class MyLinkedList {
private:
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(): val(0), next(nullptr) {}
        ListNode(int x): val(x), next(nullptr) {}
        ListNode(int x, ListNode* p): val(x), next(p) {}
    };
    int _size;
    ListNode* _dummy;

    ListNode* moveCur(int index) {
        if (index > _size || index < 0)
            return nullptr;
        ListNode* cur = _dummy;
        for (int i = 0; i < index; i++)
            cur = cur->next;
        return cur;
    }

public:
    MyLinkedList() {
        _dummy = new ListNode();
        _size = 0;
    }

    int get(int index) {
        if (index > (_size-1) || index < 0)
            return -1;
        ListNode* cur = moveCur(index);
        return cur->next->val;
    }

    void addAtHead(int val) {
        addAtIndex(0, val);
    }

    void addAtTail(int val) {
        addAtIndex(_size, val);
    }

    void addAtIndex(int index, int val) {
        ListNode* cur = moveCur(index);
        if (cur == nullptr)
            return;
        ListNode* tempAdd = new ListNode(val);
        tempAdd->next = cur->next;
        cur->next = tempAdd;
        _size++;
    }

    void deleteAtIndex(int index) {
        if (index > (_size-1) || index < 0)
            return;
        ListNode* cur = moveCur(index);
        ListNode* tempDelete = cur->next;
        cur->next = cur->next->next;
        delete tempDelete;
        _size--;
    }
};