我使用Javascript编写了一个循环链表，并检测和删除循环。在循环检测部分之前，它一直工作良好。它总是无法删除环节点。更具体地说：这段代码的removeLoop函数不起作用。
这是我的代码：
function Node(element){
this.element = element;
this.next = null;
}
//circular linked list class
function LList() {
this.head = new Node("head");
this.head.next = this.head;
this.find = find;
this.insert = insert;
this.display = display;
}
function find(item){
var curr = this.head;
while(curr.element != item){
curr = curr.next;
}
return curr;
}
//inserting items into linked list
function insert(newElem, after){
var newNode = new Node(newElem);
var curr = this.find(after);
newNode.next = curr.next;
curr.next = newNode;
}
function display() {
var currNode = this.head;
while ((currNode.next !== null) &&
(currNode.next.element !== "head")) {
console.log(currNode.next.element);
currNode = currNode.next;
}
}
function findPrevious(item){
var curr = this.head;
while(curr.next !== null && curr.next.element !== item){
curr =curr.next;
}
return curr;
}
//creating a linkedlist object
var furniture = new LList();
furniture.insert("chair","head");
furniture.insert("table", "chair");
furniture.insert("couch", "table");
furniture.insert("stool","couch");
//furniture.display();
//detecting if a linked list is circular
function detectALoop(list){
var slow = list.head;
var fast = list.head;
while(slow && fast && fast.next){
slow = slow.next;
fast = fast.next.next;
if(slow === fast){
removeLoop (slow, list);
return 1;
}
}
return 0;
}
//This part of the code doesnot work
function removeLoop(loopNode, list)
{
var ptr1 = loopNode;
var ptr2 = loopNode;
var looplen = 1,i;
// count the number of nodes in loop
while(ptr1.next != ptr2)
{
ptr1 = ptr1.next;
looplen++;
}
console.log(looplen)
ptr1 = list.head;
ptr2 = list.head;
for(i=0; i <= looplen; i++)
{
ptr2 = ptr2.next;
}
while(ptr2.next != ptr1.next)
{
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
ptr2.next = null; // breaking the loop
}
console.log(detectALoop(furniture))
furniture.display();
如果循环必须返回到第一个元素，那么这将比实际情况复杂得多。
function breakLoop(list) {
var head = list.head, tail = head, len = 1;
while (tail.next != head) {
len++;
tail = tail.next;
}
tail.next = null;
console.log(len.toString());
}
现在，如果您可能需要处理任意循环，我仍然不知道您需要3个循环做什么。使用ES6 Set；我相信，现在大多数浏览器都支持这一点。我将继续返回长度，而不是记录它。
function breakLoopAnywhere(list) {
var seen = new Set, node = list.head;
while (!seen.has(node.next)) {
seen.add(node);
node = node.next;
}
node.next = null;
return seen.size;
}
如果你没有集合，你可以用数组破解它，用indexOf替换has，用push替换add。
如果你觉得你必须有能力检测循环与非循环列表而不破坏它：
// takes a node, returns the node
// that points backwards on its next
function getLoopNode(node) {
var seen = new Set;
do {
seen.add(node);
} while (!seen.has(node.next) && node = node.next)
return node;
}
function detectLoop(node) {
return getLoopNode(node) != null;
}
function breakLoop(node) {
node = getLoopNode(node);
if (node) node.next = null;
}
您的detectALoop没有那么复杂，但它是错误的。这将检测到的唯一循环是节点2i是否循环回到节点i上。但是列表可以是3个元素，长循环到开头；它可能是许多不是CCD_ 9和CCD_。由于可能有很多数字，太多了，无法全部尝试，因此无法修复此策略。没有比我上面写的更快或更直观的聪明方法来找到图中的循环了。据我所知。
这个变量搞砸了。。。
var looplen = 1,i;
看起来你希望它是1。
您的removeLoop代码是错误的，它从未终止：
让我们假设这个列表：
A -> B -> C -> A
环路长度为3。
您正确地找到了循环长度3，然后将ptr1和ptr2设置为列表的开头，然后在ptr2上调用.next，使循环的长度增加1次（因为<=）。
// for i = 0; i <= 3
A.next -> B // i = 0
B.next -> C // i = 1
C.next -> A // i = 2
A.next -> B // i = 33
所以最后你得到了ptr2=B和ptr1=A，即ptr2===ptr1.next！
一个是另一个的下一个，在while循环中，你将两者都推进，直到一个等于另一个，但它们永远不会，因为它们总是一个，另一个！
如果您将<=更改为仅<，它是有效的，但第二个while循环实际上是无用的。