算法小白莽冲力扣day3

代码随想录算法训练营Day3

链表专题

1. 203.移除链表元素
2. 707.设计链表
3. 206.反转链表

203.移除链表元素

���们想一下如果我们需要移除单链表中的某一个元素，我们只要让该元素的next直接指向该元素的下一个元素就可以了，也就是说如果我们在链表上做删除的操作，那么就必须要知道被删除节点的前驱节点才可以。

那么既然是这样我们就需要考虑一种特殊情况了，如果我们删除的是头节点怎么办？头节点没有前驱节点呀？

针对这个问题我们就有了两种处理策略，第一个是分开写删除逻辑，第二个是我们增加一个虚拟头节点来统一删除的操作。

解法一：在原有链表上操作。

在原有链表上操作，如果移除头节点的话，我们只需要使head指向第二个节点就可以，移除非头节点我们只需使该节点前驱节点.next=该节点前驱节点.next.next。

代码如下：

class Solution{    public ListNode removeElements(ListNode head,int val){        //区分两种情况：1. 移除的节点是头节点？        //这里的头节点指的是链表的第一个节点。        while(head!=null&&head.val==val){            head=head.next;        }        ListNode cur = head;        while (cur!=null){            while(cur.next!=null&&cur.next.val==val){                //错误1：head.next=head.next.next;            cur.next=cur.next.next;            }            cur=cur.next;        }        return head;

这里我们再讨论一下移除非头节点时的边界问题，我其实这两天在做链表部分的题目使出了很多空指针异常的报错。我们要遍历这个链表，那么出循环的条件是什么？我们想一下，我们只需要指针指向最后一个节点并判断，那么我们就遍历结束了对吧？最后一个节点.next=null，那么我们可以将while条件写成while（cur.next！=null）嘛？这样写是不对的，为什么呢?我们极端点举一个例子，如果这个单链表就是一个空链表head=null，cur=head，那么在这个while（cur.next!=null），cur既然是null，那么也就不存在next，所以就会报空指针异常。

所以链表遍历的循环条件一定是cur！=null，这样才可以遍历到最后。

最后是代码中的错误1，我们一定要记得我们最后返回链表的时候，需要返回头节点，所以在处理非头节点的删除的时候不可以移动head，移动了我们就没办法返回完整的链表了。

解法2：增加一个虚拟头节点

虚拟头节点就是指向头节点的一个节点，这样链表中的每一个节点就都有了前驱节点，那这样我们就把删除节点的逻辑给统一了，即被删除节点的前驱节点直接指向被删除节点的下一个节点，这样就完成了删除操作，虚拟头节点在链表的很多题目中都有着很大的用处。

下面是代码：

ListNode vNode = new ListNode();        vNode.next=head;        ListNode cur=vNode;                while(cur.next!=null){            if(cur.next.val==val){                cur.next=cur.next.next;            }else{                cur=cur.next;            }        }        return vNode.next;

首先我们讨论一下这段代码中的返回值可不可以是head？为什么呢？因为head在我们删除操作的过程中，很可能已经被我们删除掉了，那么head是不是就为null了？这不是真正意义上的头节点。

其次我们再讨论一下这里的while循环条件为什么和上面没有虚拟头节点的不一样？刚刚不是说了这样写会出现空指针异常嘛？为什么这里不会出现？开动你聪明的大脑思考一下，这种做法和上面那个做法有什么不同呢？

不同点是什么？上面的cur最开始时是指向头节点的指针，这里的cur最开始是指向虚拟头节点的指针。

相同点是什么？不论是上面的cur还是这里的cur.next，其实都是指向头节点的指针。

707.设计链表

这道题目至我现在写这篇博客的时候还没有做出来，没有做出来的原因是我在实现addAtIndex（）方法时总会报空指针异常，我自己分析不出来，我把自己的代码贴到下面，大家帮我看看哪里有问题，救救孩子吧。

class ListNode {    int val;    ListNode next;    public ListNode() {    }    public ListNode(int val) {        this.val = val;    }}class MyLinkedList {    //链表长度    int size;    //头节点    ListNode head;    public MyLinkedList() {        //初始化操作        this.size = 0;        head = new ListNode(0);    }    public int get(int index) {        ListNode cur = head;        if (index = size) {            return -1;        } else {            for (int i = 0; i                 cur= cur.next;            }        }        //错误写法会报空指针异常，我也不知道这个为什么写到else中会报空指针异常。//            while (cur != null) {//                while (index--  0) {//                    cur = cur.next;//                }//            }//        }        return cur.val;    }    public void addAtHead(int val) {        addAtIndex(0,val);    }    public void addAtTail(int val) {        addAtIndex(size,val);    }    public void addAtIndex(int index, int val) {        //这个方法也报空指针异常了我不知道为什么        //啊啊啊啊我真的被搞得头大 这个题写了两三天了，反复的写还是有这种问题555555555。        //我分析不出来，我分析问题的能力好差呀！！！        ListNode toADD = new ListNode(val);        ListNode cur = head;        if (index > size) {            return;        }        if (index 0){            pre=cur;            cur=cur.next;        }        pre.next= cur.next;        return;    }}

206.反转列表

这道题猛地一看我们就知道只需要我们去调转指针就可以了，但是怎么去实现原地调转而不再去额外开辟一个数组空间呢？

这就需要我们去模拟一下这个调转指针的过程了，我们可以一部分一部分的分析，算啦还是看图吧。图片来自代码随想录网站。（纠正一下动画里的错误，应该是先移动pre再移动cur。）

我们先定义指针cur指向头节点，再定义指针pre初始化为null，然后还需要定义一个临时变量tmp用来保存cur.next的值，否之会丢失。这样我们就可以如图所示反转列表了，让cur.next=pre;pre=cur;cur=tmp,然后遍历链表就可以啦。

以下是代码：

class Solution {    public ListNode reverseList(ListNode head) {        ListNode cur = head;        ListNode pre =null;        ListNode tmp = null;        while (cur!=null){            tmp=cur.next;            cur.next=pre;            pre=cur;            cur=tmp;            //tmp=cur.next;如果把这句代码放这里最后执行的话也会发生空指针异常。        }        return pre;    }}

我们一起讨论一下为什么如果把tmp放后面执行会发生空指针异常？如果tmp放到while循环第一句去执行，如果cur现在指向链表最后一个元素，那么tmp=null，cur=tmp，在进入下次一循环时判断cur！=null就给拦住了对吧？

但是如果把tmp=cur.next放到最后执行，那么假设cur现在指向倒数第二个元素，

cur.next=pre;

pre=cur;

cur=tmp;

tmp=cur.next;

经过一次这样的while循环后，pre指向倒数第二个元素，cur指向倒数第一个元素，tmp=null；

然后cur！=null，进入下一次循环。

cur.next=pre;

pre=cur;

cur=tmp;

tmp=cur.next;

注意看这里的第三行cur=tmp=null;第四行调用了null.next。所以就发生了空指针异常。