刷题LeetCode第三天_leetcode listnode空指针问题

链表

LeetCode 203

1. 看到题目的第一想法
   想到了设置虚拟头结点，万一删除头结点的话，可以直接进行删除操作。
   一开始，我就想着只要cur.next.val == val的话，这时候只需要cur=cur.next.next,但是这里出现的问题就是，如果链表中的元素都是一样的，那么就没办法删除干净。

ListNode dummyHead=new ListNode();
dummyHead.next=head;
ListNode cur=head;
while(cur!=null && cur.next!=null){ //为什么判断条件这么写，不清楚
    if(cur.next.val==val){
        cur.next=cur.next.next;
    }
    cur=cur.next; //只要不相等才能执行这个语句
}
return dummyHead.next;
1
2
3
4
5
6
7
8
9
10

这里删除【7,7，7,7】最后剩下【7,7】

2. 看完题解后的想法
   除了定义出一个虚拟头结点，还要定义一个活动的节点，这个节点就指向虚拟头结点，然后开始执行循环，这里的条件是cur.next!=null为什么？因为我们要删除的是cur.next节点，所以操作这个节点的话，一定不能为空，所以要说明清楚。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return head;
        }
        ListNode dummyHead=new ListNode();
        dummyHead.next=head;
        ListNode cur = dummyHead;
        while(cur.next!=null){
            if(cur.next.val==val){
                cur.next=cur.next.next;
            }else{
                cur=cur.next;
            }
        }
        return dummyHead.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3. 遇到的困难
   这里没有考虑到给虚拟头结点也设置一个活动的节点，而且判断的条件要注意，只要涉及到要操作的节点，就要保证当前节点不是空，不然报空指针异常。

LeetCode 707

1. 看到题目的第一想法
   首先对于这种应用类的题目，需要自己设计的题目无从下手。不知道如何使用链表。

2. 看完题解后的想法
   自己定义一个链表类

class ListNode{
	int val;
	ListNode next;
	public ListNode(){}
	public ListNode(int val){
	this.val=val;
	}
}
1
2
3
4
5
6
7
8

这个要熟悉，其次在提供的类中要定义两个变量，一个是头结点，一个是链表的长度，因为在增删的时候需要修改链表的长度，代码中增加和删除的操作要注意

class ListNode{
    int val;
    ListNode next;
    public ListNode(){
    }
    public ListNode(int val){
        this.val=val;
    }
}
class MyLinkedList {
    int size;
    ListNode dummyHead;
    public MyLinkedList() {
        dummyHead = new ListNode(0);
        size=0;
    }
    
    public int get(int index) {
        if(index<0 || index>=size){ //对于index不在合理区间内要首先进行讨论
            return -1;
        }
        ListNode cur=dummyHead;
        for(int i=0;i<=index;i++){
            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) {
        if(index>size){
            return;
        }
        if(index<0){
            index=0;
        }
        size++;//这里当确定可以进行添加操作的时候，要首先进行size++的操作
        ListNode cur = dummyHead;
        ListNode newNode = new ListNode(val);
        for(int i=0;i<index;i++){
            cur=cur.next;
        }
        newNode.next = cur.next;
        cur.next = newNode;
        
    }
    
    public void deleteAtIndex(int index) {
        if(index<0 || index>=size){
            return;
        }
        size--; //确定可以删除的时候，也要先进行size--操作
        if(index==0){
            dummyHead=dummyHead.next;
            return;
        }
        
        ListNode cur = dummyHead;
        for(int i=0;i<index;i++){
            cur=cur.next;
        }
        cur.next = cur.next.next;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

3. 遇到的困难
   就是上面的size的++，–操作不是随便乱放的，否则报错。一定要在开始操作之前就已经进行++，–。

LeetCode 206

1. 看到题目的第一想法
   想着设置一个dummyhead虚拟头节点，然后设置一个cur节点一开始指向head，然后改变cur的指向，当然要保存cur.next直到指到最后一个null。但是这里我并没有注意到不需要设置一个头结点，这里只需要一个空节点。所以我盲目定义虚拟头结点，这时的虚拟头结点默认是有值的为0，而且翻转的时候，事实上第一个节点要指向空节点而不是虚拟头结点

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode dummyhead = new ListNode();
        dummyhead.next=head;
        ListNode cur=head;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next=dummyhead;
            cur=temp;
        }
        return cur.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 看完题解后的想法
   使用双指针的方法，定义pre=null，然后cur=head这时候修改cur的指向

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next=pre;
            pre = cur; //这里的顺序不能变，不然已经都修改过cur的值了再赋值给pre是有问题的
            cur = temp;
        }
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归法
这里的递归的方法，起始和双指针的思路是一样的

class Solution {
    public ListNode reverseNode(ListNode cur,ListNode pre){
        if(cur==null){
            return pre;
        }
        ListNode temp=cur.next;
        cur.next=pre;
        return reverseNode(temp,cur);//这里的两个指针的变化用了递归函数替代了而已
    }
    public ListNode reverseList(ListNode head) {
        return reverseNode(head,null);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 遇到的困难
   没有想到直接定义一个空节点pre，而且这个pre是要移动的