力扣LeetCode，移除链表元素

1 示例:
2 
3 输入: 1->2->6->3->4->5->6, val = 6
4 输出: 1->2->3->4->5

 1 package com.leetcode;
 2 
 3 /**
 4  *
 5  */
 6 public class ListNode {
 7 
 8     int val;
 9     ListNode next;
10 
11     ListNode(int x) {
12         val = x;
13     }
14 }

 1 package com.leetcode;
 2 
 3 /**
 4  * 删除链表中等于给定值 val 的所有节点。
 5  * <p>
 6  * Definition for singly-linked list.
 7  * <p>
 8  * public class ListNode {
 9  * int val;
10  * ListNode next;
11  * ListNode(int x) { val = x; }
12  * }
13  */
14 public class RemoveLinkedList {
15 
16     /**
17      * 删除链表中等于给定值 val 的所有节点。
18      * 输入: 1->2->6->3->4->5->6, val = 6
19      * 输出: 1->2->3->4->5
20      *
21      * @param head
22      * @param val
23      * @return
24      */
25     public ListNode removeElements(ListNode head, int val) {
26         // 自己实现的链表，删除链表中的某个节点，就要找到这个链表中这个节点之前的那个节点，才方便进行删除操作。
27         // 但是对于头部节点来说，没有之前的那个节点，所以就需要进行特殊处理，或者使用虚拟头节点来统一操作。
28 
29         // 方法一，不涉及头节点的时候，如何操作。
30         // 如果head本身就是val的时候，需要进行特殊处理的。
31         // 访问 head.val的时候，需要有一个前提，就是链表不为空，即head头部节点不是空的。
32 //        if (head != null && head.val == val) {
33 //            // 此时，需要对头部节点进行删除操作，此时有一定的特殊处理的。
34 //            // 删除头部节点。
35 //            ListNode delNode = head;// 将头部待删除结点保存起来。
36 //            // 此时，将头部节点head指向之前的head的下一个节点。即head = head.next。链表绕过待删除的节点。
37 //            head = head.next;
38 //            // 此时将待删除节点置空，jvm回收，此时，待删除节点和链表断开了关系。
39 //            delNode.next = null;
40 //            // 通过以上过程，删除了头部节点。
41 //        }
42 
43 
44         // 如果使用if判断的时候，可能只考虑了head不为空，且头部节点就是待删除元素，
45         // 但是如果第二个元素还是待删除元素呢，那么这里就需要使用while循环了。
46         // 循环解决了在开始部分需要删除的那些节点全部删除掉了。
47         while (head != null && head.val == val) {
48             // 此时，需要对头部节点进行删除操作，此时有一定的特殊处理的。
49             // 删除头部节点。
50             ListNode delNode = head;// 将头部待删除结点保存起来。
51             // 此时，将头部节点head指向之前的head的下一个节点。即head = head.next。链表绕过待删除的节点。
52             head = head.next;
53             // 此时将待删除节点置空，jvm回收，此时，待删除节点和链表断开了关系。
54             delNode.next = null;
55             // 通过以上过程，删除了头部节点。
56         }
57 
58         // 接下来，开始处理在中间的部分需要删除的节点。
59         // 还有，需要注意的是，这个链表中所有节点都是需要被删除的节点。
60         // 如果，此时，链表已经为空了，那么就不需要继续运行了
61         if (head == null) {
62             // 此时return head和return null是一个意思的。
63             return head;
64         }
65 
66         // 那么，接下来，开始删除链表中间的元素。
67         // 需要删除的元素等于val。需要找到待删除节点元素的前一个节点。
68         // 注意，此时的head肯定不是要被删除的节点了，它后面的节点可能是要被删除的节点。
69         ListNode prev = head;
70         // 循环遍历，此时判断，prev的下一个节点不为空，换句话说，我还没有遍历到最后一个节点元素。
71         while (prev.next != null) {
72             // 每次循环，判断下一个节点是不是需要被删除
73             if (prev.next.val == val) {
74                 // 如果prev的下一个节点的值和val相等，那么下一个节点需要被删除。
75                 // 获取到需要被删除的节点。即prev的下一个节点就是需要被删除的节点。
76                 ListNode delNode = prev.next;
77                 // 此时，让prev的下一个节点指向待删除节点元素的下一个节点。
78                 prev.next = delNode.next;
79                 // prev.next = prev.next.next;
80                 // 此时让待删除节点元素的下一个节点置空，让其和链表断开关系即可。
81                 delNode.next = null;
82                 // 经过上述步骤，就将prev.next这个节点删除掉了。
83                 // 此prev.next.val == val判断中需要注意，删除了待删除元素节点，不要将prev向下移动一个节点。
84                 // 因为，删除了prev的下一个节点之后，现在prev的下一个节点就改变了，那么改变的这个节点很可能依然是待删除元素节点。
85                 // 依然，需要走循环，判断是否是需要被删除的节点。
86             } else {
87                 // 否则，prev.next不需要被删除，就向下移动一个位置。
88                 prev = prev.next;
89             }
90         }
91         // 经过上述过程，将链表中所有元素遍历了一遍，判断是否是待删除的节点，如果是就将链表中需要被删除的节点进行删除了。
92 
93         // 最终，返回head即可。即传入的这个节点head。
94         return head;
95     }
96 
97 }

 1 package com.leetcode;
 2 
 3 /**
 4  * 删除链表中等于给定值 val 的所有节点。
 5  * <p>
 6  * Definition for singly-linked list.
 7  * <p>
 8  * public class ListNode {
 9  * int val;
10  * ListNode next;
11  * ListNode(int x) { val = x; }
12  * }
13  */
14 public class RemoveLinkedList2 {
15 
16     /**
17      * 删除链表中等于给定值 val 的所有节点。
18      * 输入: 1->2->6->3->4->5->6, val = 6
19      * 输出: 1->2->3->4->5
20      *
21      * @param head
22      * @param val
23      * @return
24      */
25     public ListNode removeElements(ListNode head, int val) {
26         // 如果使用if判断的时候，可能只考虑了head不为空，且头部节点就是待删除元素，
27         // 但是如果第二个元素还是待删除元素呢，那么这里就需要使用while循环了。
28         // 循环解决了在开始部分需要删除的那些节点全部删除掉了。
29 
30         // 使用虚拟头节点解决该问题。虚拟头节点的值传为-1了，这个值不会去访问，是多少无所谓的。
31         ListNode dummyHead = new ListNode(-1);
32         // 此时，让虚拟头节点的下一个节点执行head节点，此时dummyHead就变成了head再之前的一个节点。
33         dummyHead.next = head;
34         // 此时，这个head指向的链表中所有的节点都有前一个节点了。
35         // 我们就不需要对第一个节点进行特殊化处理了。
36 
37 
38         // 需要删除的元素等于val。需要找到待删除节点元素的前一个节点。
39         // 注意，此时的head肯定不是要被删除的节点了，它后面的节点可能是要被删除的节点。
40         ListNode prev = dummyHead;
41         // 循环遍历，此时判断，prev的下一个节点不为空，换句话说，我还没有遍历到最后一个节点元素。
42         while (prev.next != null) {
43             // 每次循环，判断下一个节点是不是需要被删除
44             if (prev.next.val == val) {
45                 // 如果prev的下一个节点的值和val相等，那么下一个节点需要被删除。
46                 // 获取到需要被删除的节点。即prev的下一个节点就是需要被删除的节点。
47                 ListNode delNode = prev.next;
48                 // 此时，让prev的下一个节点指向待删除节点元素的下一个节点。
49                 prev.next = delNode.next;
50                 // prev.next = prev.next.next;
51                 // 此时让待删除节点元素的下一个节点置空，让其和链表断开关系即可。
52                 delNode.next = null;
53                 // 经过上述步骤，就将prev.next这个节点删除掉了。
54                 // 此prev.next.val == val判断中需要注意，删除了待删除元素节点，不要将prev向下移动一个节点。
55                 // 因为，删除了prev的下一个节点之后，现在prev的下一个节点就改变了，那么改变的这个节点很可能依然是待删除元素节点。
56                 // 依然，需要走循环，判断是否是需要被删除的节点。
57             } else {
58                 // 否则，prev.next不需要被删除，就向下移动一个位置。
59                 prev = prev.next;
60             }
61         }
62         // 经过上述过程，将链表中所有元素遍历了一遍，判断是否是待删除的节点，如果是就将链表中需要被删除的节点进行删除了。
63 
64 
65         // 最终，返回head即可。即传入的这个节点head。
66         return dummyHead.next;
67     }
68 
69 }

 1 package com.leetcode;
 2 
 3 /**
 4  *
 5  */
 6 public class ListNode {
 7 
 8     int val;
 9     ListNode next;
10 
11     ListNode(int x) {
12         val = x;
13     }
14 
15     /**
16      * 将数组转换为链表结构
17      * <p>
18      * 链表节点的构造函数，使用arr为参数，创建一个链表，当前的ListNode为链表头节点。
19      * <p>
20      * 将整个链表创建完成以后，这个构造函数是一个节点的构造函数，我们最终呢，
21      * 相当于把我们的当前构造的这个节点作为头节点。
22      *
23      * @param arr
24      */
25     public ListNode(int[] arr) {
26         // 首先，判断数组arr是否合法，数组不能为空，必须包含元素
27         if (arr == null || arr.length == 0) {
28             throw new IllegalArgumentException("arr can not be empty.");
29         }
30 
31         // 让数组索引为0的元素即第一个元素赋值给存储链表节点元素的val。
32         this.val = arr[0];
33         // 遍历数组，将数组中的每一个元素都创建成新的ListNode节点。链接到前一个节点上，形成这样的一个链表。
34         // 创建一个节点，从this开始，将之后的节点都链接到此节点的后面。
35         ListNode current = this;
36         for (int i = 1; i < arr.length; i++) {
37             // 让从this开始，将之后的节点都链接到此节点的后面。
38             current.next = new ListNode(arr[i]);
39             // 让current这个几点。每次循环都向后移动一个位置，将后面的节点都依次进行挂接。
40             current = current.next;
41         }
42         // 最后，this就是我们用上面的循环创建的链表相对应的头部节点head。
43     }
44 
45     /**
46      * 为了方便在main函数中观察链表。
47      * <p>
48      * 返回的是以当前节点为头部节点的链表信息字符串。
49      * <p>
50      * 注意，这里的ListNode是一个节点哈，不是一个链表结构。
51      *
52      * @return
53      */
54     @Override
55     public String toString() {
56         StringBuilder stringBuilder = new StringBuilder();
57         // 从自身开始循环
58         ListNode current = this;
59         // 循环遍历，只要current不为空，就进行操作
60         while (current != null) {
61             // 将当前节点的val值进行拼接
62             stringBuilder.append(current.val + "->");
63             // 将current向下一个节点进行移动
64             current = current.next;
65         }
66         // 表示达到了链表的尾部。
67         stringBuilder.append("NULL");
68         return stringBuilder.toString();
69     }
70 }

  1 package com.leetcode;
  2 
  3 /**
  4  * 删除链表中等于给定值 val 的所有节点。
  5  * <p>
  6  * Definition for singly-linked list.
  7  * <p>
  8  * public class ListNode {
  9  * int val;
 10  * ListNode next;
 11  * ListNode(int x) { val = x; }
 12  * }
 13  */
 14 public class RemoveLinkedList {
 15 
 16     /**
 17      * 删除链表中等于给定值 val 的所有节点。
 18      * 输入: 1,2,6,3,4,5,6, val = 6
 19      * 输出: 1,2,3,4,5
 20      *
 21      * @param head
 22      * @param val
 23      * @return
 24      */
 25     public ListNode removeElements(ListNode head, int val) {
 26         // 自己实现的链表，删除链表中的某个节点，就要找到这个链表中这个节点之前的那个节点，才方便进行删除操作。
 27         // 但是对于头部节点来说，没有之前的那个节点，所以就需要进行特殊处理，或者使用虚拟头节点来统一操作。
 28 
 29         // 方法一，不涉及头节点的时候，如何操作。
 30         // 如果head本身就是val的时候，需要进行特殊处理的。
 31         // 访问 head.val的时候，需要有一个前提，就是链表不为空，即head头部节点不是空的。
 32 //        if (head != null && head.val == val) {
 33 //            // 此时，需要对头部节点进行删除操作，此时有一定的特殊处理的。
 34 //            // 删除头部节点。
 35 //            ListNode delNode = head;// 将头部待删除结点保存起来。
 36 //            // 此时，将头部节点head指向之前的head的下一个节点。即head = head.next。链表绕过待删除的节点。
 37 //            head = head.next;
 38 //            // 此时将待删除节点置空，jvm回收，此时，待删除节点和链表断开了关系。
 39 //            delNode.next = null;
 40 //            // 通过以上过程，删除了头部节点。
 41 //        }
 42 
 43 
 44         // 如果使用if判断的时候，可能只考虑了head不为空，且头部节点就是待删除元素，
 45         // 但是如果第二个元素还是待删除元素呢，那么这里就需要使用while循环了。
 46         // 循环解决了在开始部分需要删除的那些节点全部删除掉了。
 47         while (head != null && head.val == val) {
 48             // 此时，需要对头部节点进行删除操作，此时有一定的特殊处理的。
 49             // 删除头部节点。
 50             ListNode delNode = head;// 将头部待删除结点保存起来。
 51             // 此时，将头部节点head指向之前的head的下一个节点。即head = head.next。链表绕过待删除的节点。
 52             head = head.next;
 53             // 此时将待删除节点置空，jvm回收，此时，待删除节点和链表断开了关系。
 54             delNode.next = null;
 55             // 通过以上过程，删除了头部节点。
 56         }
 57 
 58         // 接下来，开始处理在中间的部分需要删除的节点。
 59         // 还有，需要注意的是，这个链表中所有节点都是需要被删除的节点。
 60         // 如果，此时，链表已经为空了，那么就不需要继续运行了
 61         if (head == null) {
 62             // 此时return head和return null是一个意思的。
 63             return head;
 64         }
 65 
 66         // 那么，接下来，开始删除链表中间的元素。
 67         // 需要删除的元素等于val。需要找到待删除节点元素的前一个节点。
 68         // 注意，此时的head肯定不是要被删除的节点了，它后面的节点可能是要被删除的节点。
 69         ListNode prev = head;
 70         // 循环遍历，此时判断，prev的下一个节点不为空，换句话说，我还没有遍历到最后一个节点元素。
 71         while (prev.next != null) {
 72             // 每次循环，判断下一个节点是不是需要被删除
 73             if (prev.next.val == val) {
 74                 // 如果prev的下一个节点的值和val相等，那么下一个节点需要被删除。
 75                 // 获取到需要被删除的节点。即prev的下一个节点就是需要被删除的节点。
 76                 ListNode delNode = prev.next;
 77                 // 此时，让prev的下一个节点指向待删除节点元素的下一个节点。
 78                 prev.next = delNode.next;
 79                 // prev.next = prev.next.next;
 80                 // 此时让待删除节点元素的下一个节点置空，让其和链表断开关系即可。
 81                 delNode.next = null;
 82                 // 经过上述步骤，就将prev.next这个节点删除掉了。
 83                 // 此prev.next.val == val判断中需要注意，删除了待删除元素节点，不要将prev向下移动一个节点。
 84                 // 因为，删除了prev的下一个节点之后，现在prev的下一个节点就改变了，那么改变的这个节点很可能依然是待删除元素节点。
 85                 // 依然，需要走循环，判断是否是需要被删除的节点。
 86             } else {
 87                 // 否则，prev.next不需要被删除，就向下移动一个位置。
 88                 prev = prev.next;
 89             }
 90         }
 91         // 经过上述过程，将链表中所有元素遍历了一遍，判断是否是待删除的节点，如果是就将链表中需要被删除的节点进行删除了。
 92 
 93         // 最终，返回head即可。即传入的这个节点head。
 94         return head;
 95     }
 96 
 97 
 98     public static void main(String[] args) {
 99         int[] arr = new int[]{1, 2, 6, 3, 4, 5, 6};
100         // 创建ListNode
101         ListNode head = new ListNode(arr);
102         // 打印head，注意，这里的head虽然是一个头部节点，但是覆盖了toString方法，这里的head是以head作为头部节点的整个链表对应的字符串。
103         System.out.println(head);
104         // 创建本来对象
105         RemoveLinkedList removeLinkedList = new RemoveLinkedList();
106         // 调用方法，删除待删除元素的节点
107         ListNode removeElements = removeLinkedList.removeElements(head, 6);
108         // 打印输出即可
109         System.out.println(removeElements);
110     }
111 
112 }