如何找到包含循环(循环)的链表的长度☆☆☆☆
主题:链表
回答:
- 指针A每次前进一(1)个节点。
- 指针B每次提前两(2)个节点。
- 从头开始,它们同时前进,直到B命中
null
(无循环)或A和B指向同一节点。
- 现在,只有A前进,A会再次遇到B。从您可以找到循环发言权的长度大号。
- 从头开始,这次有一个指针C首先前进L个节点,然后是指针D在它后面,每个指针一次前进一个节点。
- 当它们满足时,行进的节点D的数量L0加L等于带循环的链表的长度。
实现方式:
JAVA
package com.farenda.tutorials.algorithms.lists;
public class FloydCycleDetector {
private int position;
private int length;
private boolean cycle;
private Node head, tortoise, hare;
public void detect(Node head) {
this.head = head;
this.tortoise = this.hare = head;
this.cycle = detectCycle();
if (cycle) {
System.out.println("Found cycle.");
this.position = findPosition();
this.length = cycleLength();
} else {
System.out.println("No cycle.");
this.position = -1;
this.length = 0;
}
}
public boolean hasCycle() {
return cycle;
}
public int length() {
return length;
}
public int position() {
return position;
}
private boolean detectCycle() {
if (tortoise == null || tortoise.next == null) {
return false;
}
while (hare != null && hare.next != null) {
System.out.printf("(%d, %d),", tortoise.data, hare.data);
tortoise = tortoise.next;
hare = hare.next.next;
if (tortoise == hare) {
System.out.printf("turtle(%d) == hare(%d)%n",
tortoise.data, hare.data);
return true;
}
}
return false;
}
private int findPosition() {
int i = 1;
tortoise = head;
System.out.printf("(%d, %d),", tortoise.data, hare.data);
while (tortoise != hare) {
tortoise = tortoise.next;
hare = hare.next;
++i;
}
return i;
}
private int cycleLength() {
int i = 0;
do {
hare = hare.next;
++i;
} while (tortoise != hare);
return i;
}
}
Y
nodes = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 2)]
def next(parent):
def find(nodes, parent):
current = nodes[0]
rest = nodes[1:]
if current and current[0] == parent:
return current[1]
else:
return find(rest, parent)
return find(nodes, parent)
def next_next(x):
return next(next(x))
def meet(slow, fast, p1, p2, steps):
p1 = slow(p1)
p2 = fast(p2)
steps = steps + 1
if p1 == p2:
return (p1, steps)
else:
return meet(slow, fast, p1, p2, steps)
def meet_result(slow, fast, p1, p2):
result = meet(slow, fast, p1, p2, 0)
return result[0]
def meet_count(slow, fast, p1, p2):
result = meet(slow, fast, p1, p2, 0)
return result[1]
def find_cycle(init):
cycle_meet = meet_result(next, next_next, init, init)
cycle_root = meet_result(next, next, cycle_meet, init)
cycle_length = meet_count(lambda x: x, next, cycle_root, cycle_root)
return (cycle_meet, cycle_root, cycle_length)
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 如何找到包含循环(循环)的链表的长度☆☆☆☆
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 如何找到包含循环(循环)的链表的长度☆☆☆☆
常见问题FAQ
- 没有金币/金币不足 怎么办?
- 本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
- 所有资源普通会员都能下载吗?
- 本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。