203.移除链表元素

题目描述

原题
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点
示例 1:
1
输入:head = [1,2,6,3,4,5,6], val = 6
2
输出:[1,2,3,4,5]
Copied!
示例 2:
1
输入:head = [], val = 1
2
输出:[]
Copied!
示例 3:
1
输入:head = [7,7,7,7], val = 7
2
输出:[]
Copied!
提示:
    列表中的节点在范围 [0, 104]
    1 <= Node.val <= 50
    0 <= k <= 50

题解

递归

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode removeElements(ListNode head, int val) {
11
if(head == null)
12
return null;
13
while(head!=null && head.val==val){
14
head = head.next;
15
}
16
if(head!=null)
17
head.next = removeElements(head.next,val);
18
return head;
19
}
20
}
Copied!

迭代

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode() {}
7
* ListNode(int val) { this.val = val; }
8
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
* }
10
*/
11
class Solution {
12
public ListNode removeElements(ListNode head, int val) {
13
//创建一个模拟的头节点
14
ListNode dummyNode = new ListNode();
15
dummyNode.next = head;
16
head = dummyNode;
17
while(head!=null){
18
ListNode next = head.next;
19
//循环找到值不相等的next节点
20
while(next!=null&&next.val == val){
21
next = next.next;
22
}
23
//指向next
24
head.next = next;
25
head = next;
26
}
27
return dummyNode.next;
28
}
29
}
Copied!
1
//官方代码优化
2
class Solution {
3
public ListNode removeElements(ListNode head, int val) {
4
ListNode dummyHead = new ListNode(0);
5
dummyHead.next = head;
6
ListNode temp = dummyHead;
7
while (temp.next != null) {
8
if (temp.next.val == val) {
9
temp.next = temp.next.next;
10
} else {
11
temp = temp.next;
12
}
13
}
14
return dummyHead.next;
15
}
16
}
Copied!
最近更新 4mo ago