代码随想录第三天| 203.移除链表元素、707.设计链表、206.反转链表

第一题

• 其实这题我一直不理解为什么明明整个过程没有操作dummy，最后要返回dummy.next，
• dedug了一下发现是pre.next = cur.next;这一步的时候对dummy进行了更新，
• 之后又看了看动画演示，明白具体的操作，但还是不理解原因
• 结果我就发现我虽然不理解，但是我已经背下来了，就默写下来，看看能不能通过之后的题目再加深对链表的理解

第二题

class MyLinkedList {

    class Listnode {
        int val;
        Listnode next;

        public Listnode() {
        }

        public Listnode(int val) {
            this.val = val;
        }
    }

    int size;//链表的大小
    Listnode head;//虚拟头结点

    public MyLinkedList() {// 初始化链表
        size = 0;
        head = new Listnode(0);
    }

    //获取链表中第 index 个节点的值。如果索引无效，则返回-1
    public int get(int index) {
        if (index < 0 || index >= size) {//索引无效
            return -1;
        }
        Listnode cur = head;//定义遍历链表的指针
        for (int i = 0; i <= index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    //在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点
    public void addAtHead(int val) {
        Listnode newNode = new Listnode(val);
        newNode.next = head.next;//让新结点指向原头结点
        head.next = newNode;//虚拟结点指向头结点
        size++;
    }

    //将值为 val 的节点追加到链表的最后一个元素
    public void addAtTail(int val) {
        Listnode newNode = new Listnode(val);
        Listnode cur = head;//定义遍历链表的指针
        while (cur.next!=null){
            cur = cur.next;//此时current指向最末的一个结点
        }
        cur.next = newNode;//最末的一个结点指向新结点
        size++;
    }

    /*
     * 在链表中的第 index 个节点之前添加值为 val 的节点
     * 如果 index 等于链表的长度，则该节点将附加到链表的末尾
     * 如果 index 大于链表长度，则不会插入节点
     * 如果 index 小于0，则在头部插入节点
     */
    public void addAtIndex(int index, int val) {
        if(index>size){//如果 index 大于链表长度，则不会插入节点
            return;
        }else if(index<0){//如果 index 小于0，则在头部插入节点
            addAtHead(val);
        }else if(index==size){
            addAtTail(val);//如果 index 等于链表的长度，则该节点将附加到链表的末尾
        }else {
            Listnode newNode = new Listnode(val);//要加入的这个结点
            Listnode cur = head;//定义遍历链表的指针
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            newNode.next = cur.next;
            cur.next = newNode;
            size++;
        }
    }

    //如果索引 index 有效，则删除链表中的第 index 个节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {//索引无效
            return ;
        }
        Listnode cur = head;//定义遍历链表的指针
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        size--;
    }

}

• 也早上看的思路，晚上扣了半天，看了视频，最后发现其实逻辑还挺清晰，就是第一次看到的时候有点懵
• 太神奇了，竟然一遍过，甚至都没debug，这么长都没有报错，而且中间我还改了点东西，出息了出息了
• 就希望下次再遇到的时候能做出来吧

第三题

• 这题我是早上看的思路，吃完晚饭实现的，思路比较清晰简单
• 但是在实现的时候，返回值还是debug了一下才发现是pre，我本来写的是head，说到底还是对链表的结构理解不到位

总结

• 本来对链表就比较陌生，之前也从没用链表做过题，接触下来发现还可以，没有之前以为的那么难
• 但是今天的题没有一道是自己做出来的，都是看完题解后写的，方法也都是单链表
• 感觉今天还是有进步的，起码可以理解并用其他的方式解链表题了