代码随想录算法训练营第四天|203.移除链表元素、707.设计链表、206.反转链表

第三天是休息日

1.链表理论基础

文档讲解： 代码随想录

刷力扣题目关于链表的节点都默认定义好了，所以要注意链表的定义。

public class ListNode{
    int val;
    ListNode next;
    public ListNode(){
    }
    public ListNode(int val){
        this.val = val;
    }
    public ListNode(int val, ListNode next){
        this.val = val;
        this.next = next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.203.移除链表元素

题目链接：移除链表元素
文档讲解： 代码随想录

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //设置虚拟节点

        //判断链表是否为空
        if( head == null){
            return head;
        }

        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        ListNode cur = head;

        while(cur != null){
            if(cur.val == val){
                //节点需要删除
                pre.next = cur.next;
            }else{
                //节点不需要删除
                pre = cur;
            }
            cur = cur.next;
        }
        return dummy.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

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //不设置虚拟节点

        //判断链表head是否需要删除
        while(head != null && head.val == val){
            //要有值才能判断是否需要删除
            head = head.next;
        }

        //head为null
        while(head == null){
            return head;
        }

        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;
    }
}
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

class Solution {
    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){
                //需要考虑cur.next=null
                //此时curr不要删除，判断的是curr.next.val
                //二次循环时while，不是if，如果是if无法实现在中间节点重复val删除
                //需要删除
                curr.next = curr.next.next;
            }
            curr = curr.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

3.707.设计链表

题目链接：设计链表
文档讲解： 代码随想录

//单链表
class MyLinkedList {
    
        int size;//记录链表长度
        ListNode head;//虚拟头节点；

        //初始化链表
        public MyLinkedList(){
            size = 0;
            head = new ListNode(0);
        }
        
    public int get(int index) {
        //获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1
        if(index < 0 || index >= size){
            //下标无效
            return -1;
        }
        ListNode curNode = head;
        //链表的下标是逻辑上的，表示第几个节点
        //包含一个虚拟头节点，所以i > index停止循环
        for(int i = 0; i <= index; i++){
            curNode = curNode.next;
        }
        return curNode.val;
    }
    
    public void addAtHead(int val) {
        //将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        //将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
        addAtIndex(size, val);

    }
    
    public void addAtIndex(int index, int val) {
        //将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
        //如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
        //如果 index 比长度更大，该节点将 不会插入 到链表中。

        if(index > size){
            return;
        }
        if(index < 0){
            index = 0;
        }
        size++;//加入一个节点，size需要增加1

        //找到指向第index个节点的节点
        ListNode pre = head;
        for(int i = 0; i < index; i++){
            pre = pre.next;
        }
        
        ListNode toAdd = new ListNode(val);
        toAdd.next = pre.next;
        pre.next = toAdd;
    }
    
    public void deleteAtIndex(int index) {
        //如果下标有效，则删除链表中下标为 index 的节点。
        if(index < 0 || index >= size){
            return;
        }
        if(index == 0){
            head = head.next;
        }
        size--;
        ListNode pre = head;
        for(int i = 0; i < index; i++){
            pre = pre.next;
        }

        pre.next = pre.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

class ListNode{
    int val;
    ListNode next,prev;
    ListNode() {};
    ListNode(int val){
        this.val = val;
    }
}

class MyLinkedList {

        int size;//记录链表长度
        ListNode head, tail;//虚拟头节点、尾节点

        //初始化链表
        public MyLinkedList(){
            this.size = 0;
            this.head = new ListNode(0);
            this.tail = new ListNode(0);
            
            //保证了即使链表为空，head和tail之间仍然有一个有效的连接
            head.next = tail;
            tail.prev = head;
        }    
    
    public int get(int index) {
        //获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1
        if(index < 0 || index >= size){
            //下标无效
            return -1;
        }

        ListNode cur = this.head;
        //判断哪边找比较方便
        if(index >= size / 2){
            //从tail找
            cur = tail;
            for(int i = 0; i < size - index; i++){
                cur = cur.prev;
            }
        }else{
            //从head找
            for(int i = 0; i <= index; i++){
                cur = cur.next;
            }
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        //将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        //将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
        addAtIndex(size, val);

    }
    
    public void addAtIndex(int index, int val) {
        //将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
        //如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
        //如果 index 比长度更大，该节点将 不会插入 到链表中。

        if(index > size){
            return;
        }
        if(index < 0){
            index = 0;
        }
        size++;//加入一个节点，size需要增加1

        //找到指向第index个节点的节点
        ListNode pre = this.head;
        for(int i = 0; i < index; i++){
            pre = pre.next;
        }
        
        //新建节点
        ListNode newNode = new ListNode(val);
        newNode.next = pre.next;  
        pre.next.prev = newNode;
        newNode.prev = pre;
        pre.next = newNode;
    }
    
    public void deleteAtIndex(int index) {
        //如果下标有效，则删除链表中下标为 index 的节点。
        if(index < 0 || index >= size){
            return;
        }
        
        size--;

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

        pre.next.next.prev = pre;
        pre.next = pre.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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

3.206.反转链表

题目链接：反转链表
文档讲解： 代码随想录

//双指针
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode temp = null;
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归
        return reverse(null, head);
    }
    private ListNode reverse(ListNode pre, ListNode cur){
        if(cur == null){
            return pre;
        }

        ListNode temp = null;
        temp = cur.next;
        cur.next = pre;

        //进入下一层递归
        return reverse(cur, temp);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

从后往前的递归，我有点理解不了，之后再说吧。