Fork me on GitHub

数据结构-链表和递归

使用链表解决问题

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 ListNode {

public int val;
public ListNode next;

public ListNode(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;

// res 是头结点后面的不包含val的链表
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
//                      tail
// ↓
// ⬜⇆⬜⇆⬜⇆⬜⇆⬜⇆⬜→null
// ↑
// head
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;
}

完整代码

-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!
0%