查找链表是否包含循环的算法
迭代链表时使用快速和慢速两个指针。快速指针在每次迭代中移动两个节点,而慢速指针移动到一个节点。如果链表包含循环或循环,那么在迭代过程中,快指针和慢指针都会在某个点上相遇。如果它们不相交,并且快速或慢速将指向空,那么链表就不是循环的,它不包含任何循环。这是精确的算法
1)使用快速和慢速两个指针
2)每次迭代快速移动两个节点,慢速移动一个节点
3)如果快速和慢速相遇,则链表包含循环
4)如果fast指向空或fast.next指向空,则链表不是循环的。
下一部分包含Java程序来检查链表是否包含循环,这是上述算法的精确实现。该算法也被称为Floyd的循环查找算法,通常被称为Tortoise and Hare算法,用于查找链表中的循环。
Java程序检查链表是否为循环
这个Java程序使用LinkedList(不Java.UTI.LIKEDLIST)和链表的前一个节点类,修改了添加ToStTrn()方法和AppEntoTead()方法。另外,链表的iscyclic()方法用于实现逻辑,以确定链表是否包含循环。随后is cyclic()如果链表是循环的,则返回true,否则返回false。
/* * Java class to represent linked list data structure. */ public class LinkedList { private Node head; public LinkedList() { this.head = new Node("head"); } public Node head() { return head;} public void appendIntoTail(Node node) { Node current = head; //find last element of LinkedList i.e. tail while(current.next() != null){ current = current.next(); } //appending new node to tail in LinkedList current.setNext(node); } /* * If singly LinkedList contains Cycle then following would be true * 1) slow and fast will point to same node i.e. they meet * On the other hand if fast will point to null or next node of * fast will point to null then LinkedList does not contains cycle. */ public boolean isCyclic(){ Node fast = head; Node slow = head; while(fast!= null && fast.next != null){ fast = fast.next.next; slow = slow.next; //if fast and slow pointers are meeting then LinkedList is cyclic if(fast == slow ){ return true; } } return false; } @Override public String toString(){ StringBuilder sb = new StringBuilder(); Node current = head.next(); while(current != null){ sb.append(current).append("-->"); current = current.next(); } sb.delete(sb.length() - 3, sb.length()); // to remove --> from last node return sb.toString(); }
public static class Node { private Node next; private String data;
public Node(String data) { this.data = data; }
public String data() { return data; } public void setData(String data) { this.data = data;}
public Node next() { return next; } public void setNext(Node next) { this.next = next; }
@Override public String toString() { return this.data; } } }
|
测试循环的链表
在本节中,我们将使用带有两个链表的Java main方法测试,一个包含循环而另一个不循环。 您甚至可以为isCyclic()方法编写JUnit测试用例,以测试不同位置的循环的不同链表。 这是链表不包含任何循环的第一个测试。
/** * * Java program to find if LinkedList contains loop or cycle or not. * This example uses two pointer approach to detect cycle in linked list. * Fast pointer moves two node at a time while slow pointer moves one node. * If linked list contains any cycle or loop then both pointer will meet some time. * * @author Javin Paul */ public class LinkedListTest {
public static void main(String args[]) {
//creating LinkedList with 5 elements including head LinkedList linkedList = new LinkedList(); linkedList.appendIntoTail(new LinkedList.Node("101")); linkedList.appendIntoTail(new LinkedList.Node("201")); linkedList.appendIntoTail(new LinkedList.Node("301")); linkedList.appendIntoTail(new LinkedList.Node("401"));
System.out.println("Linked List : " + linkedList);
if(linkedList.isCyclic()){ System.out.println("Linked List is cyclic as it contains cycles or loop"); }else{ System.out.println("LinkedList is not cyclic, no loop or cycle found"); }
} }
Output: Linked List : 101-->201-->301-->401 LinkedList is not cyclic, no loop or cycle found
|
现在让我们改变链表,使其包含循环
//creating LinkedList with 5 elements including head LinkedList linkedList = new LinkedList(); linkedList.appendIntoTail(new LinkedList.Node("101")); LinkedList.Node cycle = new LinkedList.Node("201"); linkedList.appendIntoTail(cycle); linkedList.appendIntoTail(new LinkedList.Node("301")); linkedList.appendIntoTail(new LinkedList.Node("401")); linkedList.appendIntoTail(cycle);
//don't call toString method in case of cyclic linked list, it will throw OutOfMemoryError //System.out.println("Linked List : " + linkedList);
if(linkedList.isCyclic()){ System.out.println("Linked List is cyclic as it contains cycles or loop"); }else{ System.out.println("LinkedList is not cyclic, no loop or cycle found"); }
Output: Linked List is cyclic as it contains cycles or loop
|