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

Leetcode203. 移除链表元素

注意：×

1. 看起来很简单是加强版的遍历，但是注意对开头的处理和对后续的处理逻辑是不一样的，盲目的在一个while里面解决是很麻烦而且容易出错的
2. 正常解决是先一个while去掉开头的问题
3. 后续部分可以选择①一个pre节点，一个cur节点，初始化时候cur=head.next②用一个节点cur节点开始遍历以后curr.next!=null && curr.next.val == val进行判断删除
4. 一定要注意两个逻辑不相同的，不要盲目往一个while里面放，只会导致更麻烦
5. 自己的逻辑更好懂一点，用的if–else，注意看一下

/**
 * 不添加虚拟节点方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    // 已经为null，提前退出
    if (head == null) {
        return head;
    }
    // 已确定当前head.val != val
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}
/**
 * 不添加虚拟节点and pre Node方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while(head!=null && head.val==val){
        head = head.next;
    }
    ListNode curr = head;
    while(curr!=null){
        while(curr.next!=null && curr.next.val == val){
            curr.next = curr.next.next;
        }
        curr = curr.next;
    }
    return head;
}

// 自己的
    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {
            head = head.next;
        }

        ListNode dummy = head;
        while (dummy != null) {
            if (dummy.next!=null && dummy.next.val == val) {
                    dummy.next = dummy.next.next;
            }else{dummy = dummy.next;}
            
        }
        return head;
    }
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

Leetcode707.设计链表

注意：√

1. 代码一趟过，非常舒适
2. get函数部分注意cur初始的时候就是得到head.next，这里是为了得到这个下标对应的节点
3. 而addAtTail用的是size，size=3的时候，下标index最大是2，所以这里要不初始化cur的时候改一下，要不改while的判断，那肯定是改cur的初始化方便
4. addAtIndex和deleteAtIndex是为了得到cur前面一个节点，所以写法一样，去除了初始化cur部分的next

public class Solution {
    //用于存储数组中元素个数
    int size;
    // 虚拟的头结点
    ListNode head;
    public Solution() {
        size = 0;
        head = new ListNode(0);
    }

    public int get(int index) {
        // 这个函数里面的下标得反复屡清楚
        if (index>=size){return -1;}
        int i = 0;
        ListNode cur = head.next;
        while (i<index){
            cur = cur.next;
            i++;
        }
        return cur.var;
    }

    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head.next;
        head.next = newNode;
        size++;
    }

    public void addAtTail(int val) {
        ListNode newNode = new ListNode(val);
        ListNode cur = head;
        int i = 0;
        while (i<size){
            cur = cur.next;
            i++;
        }
        cur.next = newNode;
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index>size){return;}
        if (index == size){addAtTail(val);return;}

        ListNode newNode = new ListNode(val);
        int i = 0;
        // 注意这里要得到的是目标节点的上一个节点
        ListNode cur = head;
        while (i<index){
            cur = cur.next;
            i++;
        }
        newNode.next = cur.next;
        cur.next = newNode;
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index>=size){return;}
        int i = 0;
        // 注意这里要得到的是目标节点的上一个节点
        ListNode cur = head;
        while (i<index){
            cur = cur.next;
            i++;
        }
        cur.next = cur.next.next;
        size--;
    }
}

class ListNode{
    int var;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int var) {
        this.var = var;
    }

    public ListNode(int var, ListNode next) {
        this.var = var;
        this.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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

Leetcode206.反转链表

注意：×

1. 第一次错误是没有在开头打补丁，打了补丁遇到了后面的错误，最后发现根本不用补丁
2. 第二次错误是while循环判断错误，原本是写的temp来判断，是对整个逻辑没有搞清楚，总是以循环的思路去看temp
3. 第三次错误是原本的temp = temp.next;报空指针错误，这里的问题是没有理解到temp只对cur负责，只需要负责cur的下一个位置就可以了
4. 第四次错误是返回值错误，修改了前三个错误以后，cur在最后一步是等于了temp的空，这时候pre才是操作过程的最后一个节点
5. 这一题看着简单，真的是每一个坑都踩了一遍，记得再看

class Solution {
    public ListNode reverseList(ListNode head) {
//        if (head == null){return null;}
//        if (head.next == null){return head;}
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;

        while (cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
            //temp = temp.next;
        }
        //return cur;
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19