# 【203】移除链表元素
阅读量 loading
# 一、题目
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
1
2
2
# 二、题解
# 1、不使用虚拟头节点的方法
public class Solution {
/**
* 没有使用虚拟头节点的方法
*
* @param head
* @param val
* @return
*/
public ListNode removeElements(ListNode head, int val) {
// 删除掉从 head 开始都是目标数据的节点
while (head != null && head.val == val) {
head = head.next;
}
if (head == null) {
return null;
}
// 头部的目标数据删完了,删除头节点后面的为目标数据的节点
ListNode prev = head;
while (prev.next != null) {
if (prev.next.val == val) {
prev.next = prev.next.next;
} else {
prev = prev.next;
}
}
return head;
}
public static void main(String[] args) {
int[] nums = {1, 2, 6, 3, 4, 5, 6};
ListNode head = new ListNode(nums);
System.out.println(head);
ListNode result = new Solution().removeElements(head, 6);
System.out.println(result);
}
private static class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
}
public ListNode(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("array cannot be empty");
}
val = array[0];
ListNode current = this;
for (int i = 1; i < array.length; i++) {
current.next = new ListNode(array[i]);
current = current.next;
}
}
@Override
public String toString() {
StringBuilder result = new StringBuilder();
ListNode current = this;
while (current != null) {
result.append(current.val).append("->");
current = current.next;
}
result.append("null");
return result.toString();
}
}
}
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
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
运行结果:
1->2->6->3->4->5->6->null
1->2->3->4->5->null
1
2
2
# 2、使用虚拟头节点的方法
public class Solution {
/**
* 使用虚拟头节点的方法
*
* @param head
* @param val
* @return
*/
public ListNode removeElements(ListNode head, int val) {
// 虚拟头节点
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
// 因为所有的节点都具有前一个节点,所以可以直接循环
ListNode prev = dummyHead;
while (prev.next != null) {
if (prev.next.val == val) {
prev.next = prev.next.next;
} else {
prev = prev.next;
}
}
// 因为有可能头节点已经被删除了,但是头节点元素还有值,所以这里要返回虚拟头节点的 next
return dummyHead.next;
}
public static void main(String[] args) {
int[] nums = {1, 2, 6, 3, 4, 5, 6};
ListNode head = new ListNode(nums);
System.out.println(head);
ListNode result = new Solution().removeElements(head, 6);
System.out.println(result);
}
private static class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
}
public ListNode(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("array cannot be empty");
}
val = array[0];
ListNode current = this;
for (int i = 1; i < array.length; i++) {
current.next = new ListNode(array[i]);
current = current.next;
}
}
@Override
public String toString() {
StringBuilder result = new StringBuilder();
ListNode current = this;
while (current != null) {
result.append(current.val).append("->");
current = current.next;
}
result.append("null");
return result.toString();
}
}
}
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
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
运行结果:
1->2->6->3->4->5->6->null
1->2->3->4->5->null
1
2
2
# 3、使用递归解决
public class Solution {
/**
* 使用递归解决
*
* @param head
* @param val
* @return
*/
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
head.next = removeElements3(head.next, val);
return head.val == val ? head.next : head;
}
public static void main(String[] args) {
int[] nums = {1, 2, 6, 3, 4, 5, 6};
ListNode head = new ListNode(nums);
System.out.println(head);
ListNode result = new Solution().removeElements(head, 6);
System.out.println(result);
}
private static class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
}
public ListNode(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("array cannot be empty");
}
val = array[0];
ListNode current = this;
for (int i = 1; i < array.length; i++) {
current.next = new ListNode(array[i]);
current = current.next;
}
}
@Override
public String toString() {
StringBuilder result = new StringBuilder();
ListNode current = this;
while (current != null) {
result.append(current.val).append("->");
current = current.next;
}
result.append("null");
return result.toString();
}
}
}
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
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
运行结果:
1->2->6->3->4->5->6->null
1->2->3->4->5->null
1
2
2