单向、双向与循环链表和双指针应用

1. 单向链表

1.1 介绍

链表是一种递归结构,它或者为空(null),或者是指向一个节点(node)的引用,该节点还有一个元素和一个指向另一条链表的引用。

单向链表是最简单的链表结构,它的节点只包含两个域:一个数据域和指针域(用来指向下一个节点),我们可以定义节点的数据结构:

1
2
3
4
5
6
7
8
public class Node {
public Node next = null; // 指针域,用来指向下一个节点的引用
public int data; // 数据域,用来存储该节点的数据

public Node(int data) {
this.data = data;
}
}

如下图所示,节点之间通过指针域的引用将一个一个节点链接在一起,最后一个节点指向null

而且在大多数情况下,我们将使用头结点(第一个结点)来表示整个列表。

1.2 索引

与数组不同,我们无法在常量的时间内访问单链表中的随机元素。例如我们想要访问第i个元素,我们必须从头结点开始遍历,直到遍历到第i个节点:

1
2
3
4
5
6
7
8
9
10
11
12
public int get(int index) {
int j = 0;
Node p = head;
while (p != null && j < index) {
p = p.next;
j++;
}
if (p == null) { // 索引失败
return -1;
}
return p.data;
}

1.3 插入节点

例如我们想插入到第i个位置,就需要先遍历到第i - 1个节点,然后将该节点的后继指向新的节点,而新的节点的后继则指向之前的第i个节点:

1
2
3
4
5
6
7
8
9
10
11
12
13
public void addAtIndex(int index, int val) {
int j = 0;
Node p = head;
while (p != null && j < index - 1) { // 找着第index-1个节点
p = p.next;
j++;
}
if (p == null) return; // 插入失败

Node node = new Node(val); // 创建新的节点
node.next = p.next; // 将新的节点的后继节点指向原先的(index-1)的后继节点
p.next = node; // 将原先的(index-1)的后继节点指向新节点
}

插入的顺序如下:

linked_list_insert.gif

1.4 删除节点

如果我们想要删除第i个节点,只需要遍历到第i - 1个节点,然后将第i - 1个后继指向第i个节点的后继即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
public void deleteAtIndex(int index) {
int j = 0;
Node p = head;

while (p != null && j < index - 1) {
p = p.next;
j++;
}
if (p == null) return;

Node temp = p.next;
p.next = temp.next; // 让第i个结点的前驱结点的next指针指向第i个节点的后继结点
}

删除节点的顺序如下:

linked_list_delete.gif

1.5 遍历所有节点

1
2
3
4
5
6
Node p = head;
while (p != null) {
/* 对该节点一些操作 */

p = p.next;
}

2. 双链表

2.1 介绍

双链表与单链表以类似的方式工作,但是还有一个其他的引用字段:prev字段。该额外的字段用于指向当前节点的前一个节点:

TIM截图20190105151708.png

节点类DoublyListNode的结构定义为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static class DoublyListNode {
DoublyListNode prev; // 前驱
DoublyListNode next; // 后继
int val; // 节点的数据域

DoublyListNode(int e) {
this.val = e;
}

DoublyListNode(DoublyListNode prev, int e, DoublyListNode next) {
this.val = e;
this.next = next;
this.prev = prev;
}
}

JDK中LinkedList的实现就使用了双链表的数据结构,如果你感兴趣,可以看Java Notes LinkedList 源码解析

2.2 插入节点

想要删除第i个节点,和单链表的操作类似,都需要遍历到第i - 1个节点,然后用新的节点来链接第i - 1个节点和第i个节点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void addAtIndex(int index, int val) {
int j = 0;
DoublyListNode front = head;
while (front != null && j < index - 1) { // 遍历到第 i-1 个节点
front = front.next;
j++;
}
if (front == null) { // 添加位置不合理
return;
}
DoublyListNode temp = front.next; // 保留原来的第i个节点
DoublyListNode node = new DoublyListNode(val);
/* 让新的节点的前驱指向第i-1个节点,第i-1个节点的后继指向新的节点,让新的节点成为第i个节点 */
node.prev = front;
front.next = node;
/* 让新的节点的后继指向原先的第i个节点,原先第i个节点的前驱指向新的节点 */
node.next = temp;
temp.prev = node;
}

插入的顺序如下:

dobule-linked-list-add.gif

2.3 删除节点

删除节点同样和单链表的操作类似:遍历到第i - 1个节点,更改它们的前驱后继引用即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void deleteAtIndex(int index) {
int j = 0;
DoublyListNode front = head;
while (front != null && j < index - 1) { // 遍历到第i-1个节点
front = front.next;
j++;
}
if (front == null) { // 删除位置不合理
return;
}
DoublyListNode temp = front.next; // 保留原先第i个节点
/* 将第i-1个节点的后继指向第i+1个节点,第i+1个节点的前驱指向第i-1个节点 */
front.next = temp.next;
temp.next.prev = front;
}

删除的顺序如下图:

dobule-linked-list-delete.gif

2.4 遍历节点

1
2
3
4
while (p != null) {
/* 对该节点的一些操作 */
p = p.next;
}

3. 环形链表

3.1 介绍

环形链表,也成循环列表,也是一种链式的存储结构。它的最后一个结点指向头结点(或者某个节点),形成一个环。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。

cycle_linked_list.png

3.2 双指针应用

例如对于一个问题(原题见LeetCode):

1
2
3
4
5
6
给定一个链表,判断链表中是否有环。

示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

我们可以通过一个集合来记录遍历过的节点,如果后面遍历到的节点已经存在于集合中,那么说明该链表存在环:

1
2
3
4
5
6
7
8
9
10
11
12
public boolean hasCycle(ListNode head) {
Set<ListNode> nodes = new HashSet<>();
while (head != null) {
if (nodes.contains(head)) {
return true;
} else {
nodes.add(head);
}
head = head.next;
}
return false;
}

但是这题更有效的解决方法是通过双指针来实现:即一个慢指针和一个快指针

想象一下,有两个速度不同的跑步者。如果他们在直路上行驶,快跑者将首先到达目的地。但是,如果它们在圆形跑道上跑步,那么快跑者如果继续跑步就会追上慢跑者。

这正是在链表中使用双指针会遇到的不同情况:

  • 如果没有环,则快指针最终会停留在链表的末尾;
  • 如果存在环,那么快指针最终将会与慢指针相遇。

那么两个指针的速度分别是多少?

一个安全的选择是每次移动慢指针一步,而移动快指针两步。每一次迭代,快速指针将额外移动一步。如果环的长度为 M,经过 M 次迭代后,快指针肯定会多绕环一周,并赶上慢指针。

对于双指针问题,有一个解决的模板:

1
2
3
4
5
6
7
8
9
10
11
12
// 初始化快指针和慢指针
ListNode slow = head;
ListNode fast = head;
/* 更改while的条件应对特定的问题,需要注意的是防止出现空指针异常 */
while (slow != null && fast != null && fast.next != null) {
slow = slow.next; // 慢指针移动一个单位
fast = fast.next.next; // 快指针移动两个单位
if (slow == fast) { // 两个指针相遇,可以说明该链表有环
return true;
}
}
return false;

所以解决这题的更好算法是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null) {
if (fast.next == null) {
/* 如果不存在环,那么最终快指针将会最先到达尾部,此时我们可以返回false */
return false;
}
/* 慢指针slow每次移动一步,而快指针fast每次移动两步 */
fast = fast.next.next;
slow = slow.next;
if (fast == slow) { // 即慢指针和快指针刚好相遇,说明是个环形链表
return true;
}
}
return false;
}
Pushy wechat
欢迎订阅我的微信公众号