代码随想录算法训练营二十四期第三天|LeetCode203. 移除链表元素、LeetCode707. 设计链表、LeetCode 206. 反转链表

一、LeetCode203. 移除链表元素

题目链接：203. 移除链表元素
这道题可以用虚拟头节点也可以不用虚拟头节点（如果不用需要最后单独对头节点处理一下），不过不管用不用我们都要额外创建一个节点来对新链表的头节点进行定位，以免对链表进行操作以后找不到头节点。
以下是两种方法的代码：
不使用虚拟头节点：

		if(head == null) return head;//如果链表为空返回空
        ListNode node = head;//node用来定位头节点
        while(head.next != null) {//先处理头节点之后的所有节点
            if(head.next.val == val) {
                head.next = head.next.next;
                continue;
            }
            head= head.next;
        }
        if(node.val == val) return node.next;//处理头节点
        return node;
1
2
3
4
5
6
7
8
9
10
11

使用虚拟头节点：

		if(head == null) return head;//如果链表为空返回空
        ListNode node = new ListNode(0, head);//创建虚拟头节点
        ListNode node2 = node;//node2用来定位虚拟头节点
        while(node.next != null) {//使用虚拟头节点会一同处理链表的头节点，不需要额外处理
            if(node.next.val == val) {
                node.next = node.next.next;
                continue;
            }
            node = node.next;
        }
        return node2.next;//注意要返回的是虚拟头节点的下一个节点
1
2
3
4
5
6
7
8
9
10
11

二、LeetCode707. 设计链表

题目链接：707. 设计链表
我运用的是单链表来设计。
1、首先需要有一个虚拟头节点来帮助遍历链表，所以创建MyLinkedList对象时要初始化虚拟头节点：

    private ListNode node;
    public MyLinkedList() {
        node = new ListNode();
    }
1
2
3
4

根据每个部分的功能要求依次设计：
2、int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
这个很简单，只需遍历链表的同时标记当前节点的下标就可以了,我们用n来标记:

public int get(int index) {
        ListNode tem = node;//用tem来遍历整个链表
        int n = 0;//记录tem节点下一个节点的下标
        while(true) {
           ……
           n++
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9

3、void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。

public void addAtHead(int val) {
        ListNode head = new ListNode(val,node.next);
        node.next = head；
    }
1
2
3
4

4、void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
先遍历到链表尾，再让尾节点指向新节点即可：

public void addAtTail(int val) {
        ListNode node2 = new ListNode(val);
        ListNode tem = node;
        while(true) {
            ……遍历到尾节点后插入
        }

    }
1
2
3
4
5
6
7
8

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

 public void addAtIndex(int index, int val) {
        ListNode tem = node;
        int n = 0;//表示tem下一个节点的下标，也即链表的长度，虚拟头节点不算
        while(true) {
            if(tem.next == null) {//如果tem下一个节点不存在
                //……n恰好等于index时，直接插入链表尾部否则不插入
            }else {
                //……如果找到下标等于index的节点将新节点插入到该节点之前
            }
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12

6、void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

ublic void deleteAtIndex(int index) {
        ListNode tem = node;
        int n = 0;//tem下一个节点的坐标
        while(true) {
            if(tem.next != null) {//下标有效
               //……删除节点
            }else {//下标无效
                break;
            }
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12

完整代码如下：

class MyLinkedList {
    //虚拟头节点
    private ListNode node;
    //初始化
    public MyLinkedList() {
        node = new ListNode();
    }
    
    public int get(int index) {
        ListNode tem = node;//用tem来遍历整个链表
        int n = 0;//记录tem节点下一个节点的下标
        while(true) {
            if(tem.next != null) {
                if(index == n) {
                    return tem.next.val;
                }
                n++;
                tem = tem.next;
            }else {
                break;
            }
        }
        return -1;

    }
    
    public void addAtHead(int val) {
        ListNode head = new ListNode(val,node.next);
        node.next = head;

    }
    
    public void addAtTail(int val) {
        ListNode node2 = new ListNode(val);
        ListNode tem = node;
        while(true) {
            if(tem.next != null) {
                tem = tem.next;
            }else {
                tem.next = node2;
                break;
            }
        }

    }
    
    public void addAtIndex(int index, int val) {
        ListNode tem = node;
        int n = 0;//表示tem下一个节点的下标，也即链表的长度，虚拟头节点不算
        while(true) {
            if(tem.next == null) {//如果tem下一个节点不存在
                if(n == index){
                    ListNode node2 = new ListNode(val);
                    tem.next = node2;
                }
                break;
            }else {
                if(n == index) {
                    ListNode node2 = new ListNode(val, tem.next);//创建的节点next指向tem的下一个节点，也即下标为index的节点
                    tem.next = node2;//tem节点next指向新的节点
                    break;
                } else {
                    tem = tem.next;
                    n++;
                }
            }
        }

    }
    
    public void deleteAtIndex(int index) {
        ListNode tem = node;
        int n = 0;//tem下一个节点的坐标
        while(true) {
            if(tem.next != null) {//下标有效
                if(n == index) {
                    tem.next = tem.next.next;
                    break;
                }else{
                    tem = tem.next;
                    n++;
                }
            }else {//下标无效
                break;
            }
        }

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

三、LeetCode 206. 反转链表

题目链接： 206. 反转链表
反转链表，这里要运用到递归回溯的算法思想。
通过递归遍历到链表的尾节点，然后将尾节点反转（同时将其标记下来，因为这是反转后链表的头节点)，随后回溯到上一层节点再将其反转，直到回溯到头节点。
代码如下：

class Solution {
    private ListNode node;//用来标记尾节点，也就是反转之后的头节点
    public ListNode travel(ListNode tem) {
        if(tem == null) return null;//如果传进来的是空链表，直接返回空
        if(tem.next == null){//如果传进来的是链表尾节点，定位尾节点，然后将尾节点返回
            node = tem;
            return tem;
        }

        ListNode node2 = travel(tem.next);//node2接受下一节做参数点返回的节点(返回的其实就是下一节点，不过它指向的是空节点)
        node2.next = tem;//将node2指向当前节点；
        tem.next = null;//将当前节点指向空节点，实际就是为了回溯到上级时指向上级的当前节点，也就是前一个节点
        return tem;//返回当前节点
    }
    public ListNode reverseList(ListNode head) {
        travel(head);//这里不需要变量去接受，实际上它返回的就是反转之后的最后一个节点
        return node;//我们要返回的时之前就定位好的反转之后的新头节点
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结

对于链表的操作，最好是定义一个虚拟头节点，这样比较方便而且逻辑更清晰。