0%

Java算法与数据结构之单向环形链表

单向环形链表

循环链表

循环链表跟单链表的区在尾结点指针是指向链表的头结点。和单链表相比,循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时,采用循环链表实现代码会简洁很多。

Josephu问题

N个人坐成一个圆环(编号为1 - N),从第1个人开始报数✋,数到K的人出列,后面的人重新从1开始报数。问最后剩下的人的编号。

👉思路:

用一个不带头结点的循环链表来处理Josephu 问题:先构成一个有n个结点的单循环链表,然后由k结点起从1开始计数,计到m时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束。

约瑟夫环 51Nod - 1073

例如:N = 3,K = 2。2号先出列,然后是1号,最后剩下的是3号。

Input

1
2个数N和K,表示N个人,数到K出列。(2 <= N, K <= 10^6)

Output

1
最后剩下的人的编号

Sample Input

1
3 2

Sample Output

1
3

对于这道OJ题可以通过递归的方法,找到其中的规律便可AC,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int ans = 0;
for (int i = 2; i <= n; i++) {
ans = (ans + k) % i;
}
System.out.println(ans + 1);
}
}

👉以此题为例,使用单项循环链表的方式实现,但是不能作为此题AC的代码,会超时!思路如下:

首先构建一个单向的环形链表

  1. 先创建第一个节点, 让 first 指向该节点,并形成环形⚪
  2. 后面当我们每创建一个新的节点,就把该节点,加入到已有的环形链表中即可.f

然后进行报数出圈

  1. 需要创建一个辅助指针(变量) helper , 首先让其指向环形链表的最后这个节点
  2. 当开始报数时,让first 和 helper 指针同时 的移动 k - 1 次 🐌🐌
  3. 这时就可以将first 指向的节点 出圈
    first = first .next
    helper.next = first
  4. 然后直到圈内只有最后一个人,即最后一个节点的时候(first == helper)结束循环🔄
  5. 最后的first中的编号即为最后一个人的编号
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
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
addNode(n);
countNode(n, k);

}
public static Node first = null;
public static void addNode(int nums) {
Node current = null; // 辅助指针
//创建一个循环链表
for (int i = 1; i <= nums; i++) {
Node node = new Node(i);
if (i == 1) { //first指向第一个孩子
first = node;
first.next = first;
current = first; //
} else {
current.next = node;
node.next = first;
current = node;
}
}
}

public static void countNode(int nums, int k) {
//创建一个辅助指针helper
Node helper = first;
//需要创建一个辅助指针helper,事先应该指向环形链表的最后这个节点
while (true) {
if (helper.next == first) { //说明helper指向最后一个节点
break;
}
helper = helper.next;
}
//当报数时,让first 和 helper指针同时移动 k- 1次,然后出圈
//这是一个循环操作,直到圈中只有一个节点
while (true) {
if (first == helper) {//说明圈中只有一个节点
break;
}
for (int i = 0; i < k - 1; i++) {
first = first.next;
helper = helper.next;
}
//这是first指向的节点,就是要出圈的节点
first = first.next;
helper.next = first;
}
System.out.println(first.no);
}
}

//创建一个Node节点类
class Node {
public int no;
public Node next;
public Node(int no) {
this.no = no;
}
}
北以晨光 wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
------ 本文结束感谢您的阅读 ------