代码随想录算法训练营第三天 | LeetCode203移除链表元素、707计划链表、206 ...

203.移除链表元素：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路：思路比较简单，从头到尾遍历，某节点的下一个节点的val值若等于给定的整数val，则另该节点的next指向该节点下一个节点的next。
编码中的题目：
1、刚开始怀疑是检查此时的节点照旧该节点的下一个节点，照旧都可以。稍微一想，若检查的是该节点，由于是单向链表，下一个节点无法被前一个节点指向，所以肯定是检查下一个节点的值；
2、使用了两个while循环，总感觉怪怪的。写完后发现时间不太理想，对了答案后发现了题目，一会再总结。
我的代码，AC，注释里是第一次AC的代码，不好且更慢

1. class Solution {
2.     public ListNode removeElements(ListNode head, int val) {
3.         if(head == null)
4.             return null;
5.         ListNode list = head;
6.         while(list.val == val){
7.             list = list.next;
8.             if(list == null)
9.                 return null;
10.         }
11.         head = list;
12.         // while(list.next != null){
13.         //     while(list.next != null && list.next.val == val){
14.         //         list.next = list.next.next;
15.         //     }
16.         //     if(list.next != null)
17.         //         list = list.next;   
18.         // } 修改前的代码，想在一个while里解决下一个节点是null或.next.next.val=val，时间不好
20.         //修改while条件并将内部的while改成if，可以在下轮循环解决null和=val的问题，更快
21.         while(list.next != null){
22.             if(list.next.val == val)
23.                 list.next = list.next.next;
24.             else
25.                 list = list.next;
26.         }
27.         return head;
28.     }
29. }

复制代码

参考答案：加上两种其他思路，参加虚拟头指针和递归：代码随想录

1. public ListNode removeElements(ListNode head, int val) {
2.     while(head!=null && head.val==val) {
3.         head = head.next;
4.     }
5.     ListNode curr = head;
6.     while(curr!=null && curr.next !=null) {
7.         if(curr.next.val == val){
8.             curr.next = curr.next.next;
9.         } else {
10.             curr = curr.next;
11.         }
12.     }
13.     return head;
14. }

复制代码

1. public ListNode removeElements(ListNode head, int val) {
2.     // 设置一个虚拟的头结点
3.     ListNode dummy = new ListNode();
4.     dummy.next = head;
6.     ListNode cur = dummy;
7.     while (cur.next != null) {
8.         if (cur.next.val == val) {
9.             cur.next = cur.next.next;
10.         } else {
11.             cur = cur.next;        
12.         }
13.     }
14.     return dummy.next;
15. }

复制代码

1. class Solution {
2.     public ListNode removeElements(ListNode head, int val) {
3.         if (head == null) {
4.             return head;
5.         }
7.         // 假设 removeElements() 返回后面完整的已经去掉val节点的子链表
8.         // 在当前递归层用当前节点接住后面的子链表
9.         // 随后判断当前层的node是否需要被删除，如果是，就返回
10.         // 也可以先判断是否需要删除当前node，但是这样条件语句会比较不好想
11.         head.next = removeElements(head.next, val);
12.         if (head.val == val) {
13.             return head.next;
14.         }
15.         return head;
17.         // 实际上就是还原一个从尾部开始重新构建链表的过程
18.     }
19. }

复制代码

反思：注释掉的自己刚开始写的代码的题目：一是外层while的条件不好，我想进入下一个while前肯定要移到下一个节点，所以必须判定；二是用了第二个while，担心连着几个节点都=val，再加上前一个题目，移动到下一个节点，外层while又没有判定自身，便会忽略掉连着的=val的节点。现实上不是每次循环都要到下一个节点，若删除了下一个节点，那么此次只将next设置为再下一个节点，并不移动到下一个节点，然后通过下一次while的条件和if判定是否要举行移动，是否为null。第二中设置虚拟头指针是为了跳过对头指针的判定，将头指针按照其他普通节点举行处理处罚。第三种递归方法相当于从后往前构造新的链表，以我目前的水平应该只能看懂但自己想不到。

707.计划链表：标题比较长，可以直接看LeetCode官网：707. 计划链表 - 力扣（LeetCode）

思路：我对计划数据结构这块不太熟悉，选择边看解析边写。选择计划双向链表，先贴代码：

1. class MyLinkedList {
3.     private int size;
4.     private ListNode head;
5.     private ListNode tail;
7.     class ListNode{
8.         int val;
9.         ListNode prev;
10.         ListNode next;
11.         ListNode(int val){
12.             this.val = val;
13.         }
14.     }
16.     public MyLinkedList() {
17.         this.size = 0;
18.         this.head = new ListNode(0);
19.         this.tail = new ListNode(0);
20.         this.head.next = this.tail;
21.         this.tail.prev = this.head;
22.     }
23.    
24.     public int get(int index) {
25.         if(index < 0 || index >= size)
26.             return -1;
27.         ListNode cur = head;
28.         if(size / 2 > index){
29.             for(int i=0;i<=index;i++)
30.                 cur = cur.next;
31.         }else{
32.             cur = tail;
33.             for(int i=0;i<size-index;i++)
34.                 cur = cur.prev;
35.         }
36.         return cur.val;
37.     }
38.    
39.     public void addAtHead(int val) {
40.         addAtIndex(0,val);
41.     }
42.    
43.     public void addAtTail(int val) {
44.         addAtIndex(size,val);
45.     }
46.    
47.     public void addAtIndex(int index, int val) {
48.         if(index > size || index < 0){
49.             return;
50.         }
51.         // 在第n个节点前插入，要找的是第n-个节点，不然单向链表找不到前一个，不能用next指向
52.         ListNode cur = head;
53.         for(int i=0;i<index;i++)
54.             cur = cur.next;
55.         ListNode new_node = new ListNode(val);
56.         // 注意顺序
57.         new_node.next = cur.next;
58.         cur.next.prev = new_node;
59.         new_node.prev = cur;
60.         cur.next = new_node;
61.         size++;        
62.     }
63.    
64.     public void deleteAtIndex(int index) {
65.         if(index >= size || index < 0){
66.             return;
67.         }
68.         // 同上找前一个
69.         ListNode cur = head;
70.         for(int i=0;i<index;i++)
71.             cur = cur.next;
72.         // 注意顺序
73.         cur.next.next.prev = cur;
74.         cur.next = cur.next.next;
75.         size--;
76.     }
77. }
79. /**
80. * Your MyLinkedList object will be instantiated and called as such:
81. * MyLinkedList obj = new MyLinkedList();
82. * int param_1 = obj.get(index);
83. * obj.addAtHead(val);
84. * obj.addAtTail(val);
85. * obj.addAtIndex(index,val);
86. * obj.deleteAtIndex(index);
87. */

复制代码

计划链表类，也就是计划内里的属性和方法。标题已经给出了全部的方法名，那我们先根据方法名大致推测下必要什么属性。起首作为链表内部肯定有很多节点，这里的节点是要我们自己计划的。于是创建ListNode类，根据题意且我们是双链表，那么Node类型必要一个val，一个prev节点和一个next节点，以及一个构造函数。然后思量整个链表，我们使用虚拟头尾节点的方式构建链表，这样可以方便后续的删改，详细原因可看代码或者手把手带你学会操纵链表 | LeetCode：203.移除链表元素_哔哩哔哩_bilibili。于是参加ListNode类型的虚拟头尾节点，再根据题意，方法中要判定输入的值是否越界，也就是否超过了链表大小，于是再参加size。
对于方法而言，起首是类的构造函数，一个无参构造函数即可，留意要先链接首尾节点。然后是一个get方法，判定完是否越界后，判定index与size的大小关系选择从后往前查照旧从前往后，随后就是一个简单的遍历，不过要留意边界条件，因为我们是从虚拟节点开始的。
然后先思量addAtIndex方法，判定完index开始遍历，留意在index前插入节点，我们要找的就是index前的一个节点，把新结点插在它和index之间，如果找到index位置，可以让它指向index，但不能让index前的节点指向它。而插入部分则要留意顺序，先让新节点指向该指向的位置，再让原链表的节点指向它，否则会因为连接关系被修改而找不到。
前面的addAtHead和addAtTail，就是特别情况的addAttIndex，传入头尾即可。最后的deleteAtIndex则和addAtIndex差不多，留意index不能等于size，删除的指向顺序。

206.反转链表：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路：第一反应是用上一题没想出来的递归，因为我想似乎递归都是从最后一次往前推进的，很契合标题中从尾指向头的目的，钻研了很久照旧克服了。做完后看解析发现我的思路是从后往前的递归。
编码中碰到的题目：
1、成环了陷入死循环。这是由于没有断开之前前一项指向后一项的next，补充一行就行；
2、我之前的代码返回的是之前的前一个/反转后的后一个，导致最后return的是之前的头节点/反转后的尾节点，这样显然是不正确的。后面想了很久，原来反转后的头节点是可以从第一次递归不停传到竣事的，感觉这有点不符合我如今理解中的递归的常理。同时在反转的时间，可以假设前面都没反转，后面都反转，1->2->3<-4<-5这样，反转操纵就是cur.next(4).next=3即可
我的代码，AC:（注释里的是之前的错误）

1. class Solution {
2.     public ListNode reverseList(ListNode head) {
3.         if(head ==null || head.next == null)
4.             return head;
5.         ListNode cur = reverseList(head.next);
6.         // cur.next = head;
7.         head.next.next = head;
8.         head.next = null;
9.         // return head;
10.         return cur;            
11.     }
12. }

复制代码

参考答案，附上通例一些的双指针解法：

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

复制代码

反思：我用的反向递归法主要是编码过程中的那两个题目转过弯来了就照旧比较好理解。双指针法固然基础，但我刚看的时间总是想不明白cur为什么会同时next指向prev和后面的（似乎这就是我大一数据结构没学好链表的原因之一，听上去是个若只题目但就是没想明白）。最后想明白了，画个图留档：

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。