leetcode 203号问题
1
2
3
4
5
6
|
Remove all elements from a linked list of integers that have value val.
Example:
Input: 1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5
|
给定的节点
1
2
3
4
5
6
7
8
9
|
public class {
public int val;
public ListNode next;
public (int x) {
val = x;
}
}
|
不使用虚拟头结点
如果链表头部是需要删除的元素, 直接进行删除, 直到整个链表删除完或者链表头不是需要删除的元素为止; 然后开始删除头结点后面需要删除的元素
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
|
class Solution {
public ListNode removeElements(ListNode head, int val) {
while(head != null && head.val == val){
ListNode delNode = head;
head = head.next;
delNode.next = null;
}
if(head == null)
return head;
ListNode prev = head;
while(prev.next != null){
if(prev.next.val == val) {
ListNode delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
}
else
prev = prev.next;
}
return head;
}
}
|
另一种方法是既然头部是需要删除的节点, 就直接跳过去, 不去管它, 那么整个链表剩下的就是头结点不需要删除的了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public ListNode removeElements(ListNode head, int val) {
while(head != null && head.val == val)
head = head.next;
if(head == null)
return head;
ListNode prev = head;
while(prev.next != null){
if(prev.next.val == val)
prev.next = prev.next.next;
else
prev = prev.next;
}
return head;
}
|
使用虚拟头结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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;
}
return dummyHead.next;
}
|
递归
本质上是将原来的问题转化为更小的同一问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public ListNode removeElements(ListNode head, int val) {
if(head == null)
return head;
ListNode res = removeElements(head.next, val);
if(head.val == val)
return res;
else{
head.next = res;
return head;
}
}
|
化简
1
2
3
4
5
6
7
8
|
public ListNode removeElements(ListNode head, int val) {
if(head == null)
return head;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
|
其他结构的链表
双向链表
在双向链表中, 每个节点都有两个指针, 一个指向下一个节点, 一个指向前一个节点
1
2
3
4
5
6
7
8
9
|
class Node{
E e;
Node next, prev;
}
|
循环链表
循环链表的尾结点指向的是头结点
1
2
3
4
|
class Node{
E e;
Node next, prev;
}
|
数组链表
使用数组来实现链表, 存储的是元素和下一个节点的下标
1
2
3
4
|
class Node{
E e;
int index;
}
|
完整代码
近期评论