How to detect a loop in a linked list?

Question

Say you have a linked list structure in Java. It's made up of Nodes:

class Node {
    Node next;
    // some user data
}

and each Node points to the next node, except for the last Node, which has null for next. Say there is a possibility that the list can contain a loop - i.e. the final Node, instead of having a null, has a reference to one of the nodes in the list which came before it.

What's the best way of writing

boolean hasLoop(Node first)

which would return true if the given Node is the first of a list with a loop, and false otherwise? How could you write so that it takes a constant amount of space and a reasonable amount of time?

Here's a picture of what a list with a loop looks like:

Stickseed

Wow..I would love to work for this employer finite amount of space and a reasonable amount of time? :) – Swept

If the list has a loop, there is no first node. – Zonate

Yes, sorry, I meant finite as in "not related to the size of the list"... How should I put it.... I'll re-edit. – Stickseed

@Zonate - the loop doesn't necessary loop back to the first node. It can loop back to halfway. – Stickseed

you should somehow mark nodes walked over if next node has the mark - you have found a loop – Slovak

Turtle and Rabbit algorithm will solve it. – Quenna

The answers below are worth reading, but interview questions like this are terrible. You either know the answer (i.e. you've seen a variant on Floyd's algorithm) or you don't, and it doesn't do anything to test your reasoning or design ability. – Obeng

To be fair, most of "knowing algorithms" is like this -- unless you're doing research-level things! – Voiceless

Agree. If this was an actual interview question or homework assignment given to me, I'd put a marker into the Node class and do a trivial implementation of hasLoop(). Only if I'm explicitly not allowed to change the node implementation I'd bother with the more advanced cycle-finding algorithms. – Stratagem

@Voiceless - Yes, most interesting algorithms fall in to the "you'll likely never figure it out, just learn as much as you can" category so asking someone to figure one out in an interview seems like a bad idea. It tells you nothing about how they approach problems, and only confirms whether they have read about that particular algorithm before. – Obeng

Do you know the length of the list? (Number of nodes) – Briones

@Obeng And yet it would be revealing to know what they would do when they did not know the answer. E.g. what steps would they take, who would they work with, what would they do to overcome a lack of algorithmec knowledge? – Estimate

But then its not a constant amount of space. you're adding O(n) memory requirement. – Boulevardier

i'll mark walked over node by destroing it's next value (assign for example to 0x1); if i'll found node with destoyed next value => there was a loop in this queue :) – Slovak

[Brent's Cycle Detection Algorithm](siafoo.net/algorithm/11 ) – Fidellia

"Destroying" the next value is not correct, as it has to be an object of type Node (0x1 wont work) and it cannot be null (which stands for the end of the list). Create one global, list-unrelated instance of Node and call it 'visited'. Then traverse the list and for every visited Node, do "this.next=visited;". If you ever encounter a node with next==visited (yes, "=="), you have a loop. And the 'added' memory requirement is exactly 1 object. – Diverticulum

But how would you initialize this marker each time the method is called? – Rotifer

can anybody please elaborate approach to find the node which has loop. eg: In above example node 3 is required node. – Polymeric

possible duplicate of How to determine if a linked list has a cycle using only two memory locations – Neolatin

I was asked this question in MindTree interview. – Braeunig

Answer 1

You can make use of Floyd's cycle-finding algorithm, also known as tortoise and hare algorithm.

The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes.

• If the linked list has a loop they will definitely meet.
• Else either of the two references(or their next) will become null.

Java function implementing the algorithm:

boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list

    while(true) {

        slow = slow.next;          // 1 hop

        if(fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false;          // next node null => no loop

        if(slow == null || fast == null) // if either hits null..no loop
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop
            return true;
    }
}

Swept

Okay, but at the moment you have fast just hopping once - doesn't it need to do fast = fast.next.next? – Stickseed

Also need to do a null-check on fast.next before calling next again: if(fast.next!=null)fast=fast.next.next; – Stevenage

you should check not only (slow==fast) but: (slow==fast || slow.next==fast) to prevent jumping the fast over the slow – Slovak

@oraz: Even if they jump they will finally meet again later. But yes we can do this check as an optimization. – Swept

i was wrong: fast can't jump over slow, because to jump over slow on next step fast should has the same pos as slow :) – Slovak

The check for slow == null is redundant unless the list has just one node. You can also get rid of one call to Node.next. Here's a simpler and faster version of the loop: pastie.org/927591 – Azzieb

You should really cite your references. This algorithm was invented by Robert Floyd in the '60s, It's known as Floyd's cycle-finding algorithm, aka. The Tortoise and Hare Algorithm. – Examination

This code won't work for odd length lists. If fast.next == null then the element fast refers to is never advanced. After some time, the slow reference will catch up and falsely report a loop. – Offcolor

Tim is right, don't use this solution as is! Scary that such a broken solution would get voted so high. – Rotifer

@codaddict, Very nice algorithm. – Catholicism

are they comparing values or references ? because dups can be there in a list – Catharine

@Catharine - It is comparing whether or not they point to NULL (i.e. no more nodes, so the list must NOT loop. Cause it hit the end). Or it compares if they reference ("point") to the same object (same Node). If they point to the same node, it implies the faster one looped around long enough for the slow guy to catch up and enter the loop. – Caviness

I think the approach should be stated in terms of time and space complexity tradeoffs. If space complexity is not a concern, this approach is unnecessarily complicated - i.e. a speed of traversal differential compared to very simple code that checks for a duplicate pointer reference in a set. – Brander

The check for slow == null is redundant. But other than that this a nice implementation of Floyd's algorithm. – Endblown

Surely hashing (or specifically, a HashMap, since we're talking Java) would be a better solution (you'll detect the loop the instant you encounter it, instead of whenever the two references happen to coincide) in any scenario that's not memory-constrained by the size of the list (or artificial constraints tacked onto the question)? – Wrac

If slow and fast are references to the same object shouldn't any modification to slow also affect fast? – Lallage

Answer 2

Here's a refinement of the Fast/Slow solution, which correctly handles odd length lists and improves clarity.

boolean hasLoop(Node first) {
    Node slow = first;
    Node fast = first;

    while(fast != null && fast.next != null) {
        slow = slow.next;          // 1 hop
        fast = fast.next.next;     // 2 hops 

        if(slow == fast)  // fast caught up to slow, so there is a loop
            return true;
    }
    return false;  // fast reached null, so the list terminates
}

Rotifer

Nice and succinct. This code can be optimized by checking if slow == fast || (fast.next != null && slow = fast.next); :) – Fudge

@Fudge That's not an optimization. If slow == fast.next then slow will equal fast on the very next iteration; it only saves one iteration at most at the expense of an additional test for every iteration. – Heraldry

@ana01 slow cannot become null before fast as it is following the same path of references (unless you have concurrent modification of the list in which case all bets are off). – Rotifer

Out of curiosity how does this work for odd numbers? Can't hare still pass the turtle on odd length linked lists? – Reactance

@Reactance Each iteration of the loop the hare gets 1 step further ahead of the turtle. So if the hare is behind by 3 steps, then the next iteration it takes two hops and the turtle takes one hop, and now the hare is behind by 2 steps. After the next iteration the hare is behind by 1 hop, and then it's caught up exactly. If the hare took 3 hops while the turtle took one, then it could skip by because it would be gaining by 2 each time, but since it only gains by 1 each iteration it cannot skip past. – Rotifer

Yes, it's the same after the accepted answer was corrected to match this one. – Rotifer

Answer 3

Better than Floyd's algorithm

Richard Brent described an alternative cycle detection algorithm, which is pretty much like the hare and the tortoise [Floyd's cycle] except that, the slow node here doesn't move, but is later "teleported" to the position of the fast node at fixed intervals.

The description is available at Brent's Cycle Detection Algorithm (The Teleporting Turtle). Brent claims that his algorithm is 24 to 36% faster than the Floyd's cycle algorithm. O(n) time complexity, O(1) space complexity.

public static boolean hasLoop(Node root) {
    if (root == null) return false;
    
    Node slow = root, fast = root;
    int taken = 0, limit = 2;
    
    while (fast.next != null) {
        fast = fast.next;
        taken++;
        if (slow == fast) return true;
        
        if (taken == limit) {
            taken = 0;
            limit <<= 1;    // equivalent to limit *= 2;
            slow = fast;    // teleporting the turtle (to the hare's position) 
        }
    }
    return false;
}

Ceroplastic

This answer is awesome! – Epicontinental

Really liked your answer, included it on my blog - k2code.blogspot.in/2010/04/…. – Jointure

Answer 4

An alternative solution to the Turtle and Rabbit, not quite as nice, as I temporarily change the list:

The idea is to walk the list, and reverse it as you go. Then, when you first reach a node that has already been visited, its next pointer will point "backwards", causing the iteration to proceed towards first again, where it terminates.

Node prev = null;
Node cur = first;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}
boolean hasCycle = prev == first && first != null && first.next != null;

// reconstruct the list
cur = prev;
prev = null;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

return hasCycle;

Test code:

static void assertSameOrder(Node[] nodes) {
    for (int i = 0; i < nodes.length - 1; i++) {
        assert nodes[i].next == nodes[i + 1];
    }
}

public static void main(String[] args) {
    Node[] nodes = new Node[100];
    for (int i = 0; i < nodes.length; i++) {
        nodes[i] = new Node();
    }
    for (int i = 0; i < nodes.length - 1; i++) {
        nodes[i].next = nodes[i + 1];
    }
    Node first = nodes[0];
    Node max = nodes[nodes.length - 1];

    max.next = null;
    assert !hasCycle(first);
    assertSameOrder(nodes);
    max.next = first;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = max;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = nodes[50];
    assert hasCycle(first);
    assertSameOrder(nodes);
}

Skein

Does the reverse work correctly when loop is pointing to any node other than first ? If the initial linked list is like this 1->2->3->4->5->2 (with a cycle from 5 to 2), then the reversed list looks like 1->2<-3<-4<-5 ? And if the reverse is that , the final reconstructed list will be screwed up ? – Geier

@Zenil: That why I wrote that last testcase, where the last node points to the middle of the list. If reconstruction would not work, that test would fail. About your example: the reversal of 1->2->3->5->2 would be 1->2->5->4->3->2, because the loop only stops once the end of the list has been reached, not when the end of the loop (which we can not easily detect) has been reached. – Skein

Answer 5

Tortoise and hare

Take a look at Pollard's rho algorithm. It's not quite the same problem, but maybe you'll understand the logic from it, and apply it for linked lists.

(if you're lazy, you can just check out cycle detection -- check the part about the tortoise and hare.)

This only requires linear time, and 2 extra pointers.

In Java:

boolean hasLoop( Node first ) {
    if ( first == null ) return false;

    Node turtle = first;
    Node hare = first;

    while ( hare.next != null && hare.next.next != null ) {
         turtle = turtle.next;
         hare = hare.next.next;

         if ( turtle == hare ) return true;
    }

    return false;
}

(Most of the solution do not check for both next and next.next for nulls. Also, since the turtle is always behind, you don't have to check it for null -- the hare did that already.)

Voiceless

Answer 6

In this context, there are loads to textual materials everywhere. I just wanted to post a diagrammatic representation that really helped me to grasp the concept.

When fast and slow meet at point p,

Distance travelled by fast = a+b+c+b = a+2b+c

Distance travelled by slow = a+b

Since the fast is 2 times faster than the slow. So a+2b+c = 2(a+b), then we get a=c.

So when another slow pointer runs again from head to q, at the same time, fast pointer will run from p to q, so they meet at the point q together.

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next==null)
        return null;

    ListNode slow = head;
    ListNode fast = head;

    while (fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;

        /*
        if the 2 pointers meet, then the 
        dist from the meeting pt to start of loop 
        equals
        dist from head to start of loop
        */
        if (fast == slow){ //loop found
            slow = head;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }            
    }
    return null;
}

Phenacite

A picture worths more than thousands of words. Thanks for the neat and simple explanation ! – Araxes

Best explanation on internet. Would just add that this proves that fast and slow pointer converge after linear time – Ligan

if a is bigger than loop length then fast will make multiple loop and formula distance (fast) = a + b + b + c will change to a + (b+c) * k + b introducing extra parameter k that counts number of lopps made by fast one. – Anatolia

Answer 7

The user unicornaddict has a nice algorithm above, but unfortunately it contains a bug for non-loopy lists of odd length >= 3. The problem is that fast can get "stuck" just before the end of the list, slow catches up to it, and a loop is (wrongly) detected.

Here's the corrected algorithm.

static boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either.
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list.

    while(true) {
        slow = slow.next;          // 1 hop.
        if(fast.next == null)
            fast = null;
        else
            fast = fast.next.next; // 2 hops.

        if(fast == null) // if fast hits null..no loop.
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}

Docia

Answer 8

Algorithm

public static boolean hasCycle (LinkedList<Node> list)
{
    HashSet<Node> visited = new HashSet<Node>();

    for (Node n : list)
    {
        visited.add(n);

        if (visited.contains(n.next))
        {
            return true;
        }
    }

    return false;
}

Complexity

Time ~ O(n)
Space ~ O(n)

Attachment

How is space complexity O(2n)? – Stinger

@user3543449 you're right, it should be just n, fixed – Attachment

This is actually time ~ O(n^2) since each contains check for an ArrayList takes O(n) and there are O(n) of them. Use a HashSet instead for linear time. – Rotifer

This doesn't test for cycles but for duplicate values using the elements equals and hashCode. It's not the same thing. And it dereferences null on the last element. And the question didn't say anything about storing the nodes in a LinkedList. – Chemosphere

@Chemosphere n.next is a reference, not a value. we're checking for duplicate reference not duplicate values. n.next can be null, n shouldn't be null. – Attachment

@KhaledKhnifer: You're right. I don't know what I was thinking when wrote my last comment, I must have been drunk or something. Sorry about that! – Chemosphere

Your answer is a bit weird however, because it assumes that the OP has the custom linked list stored in a java.util.LinkedList. – Chemosphere

@Chemosphere it's a pseudo-code, that's not a Java code, that's why I titled it with Algorithm – Attachment

Answer 9

The following may not be the best method--it is O(n^2). However, it should serve to get the job done (eventually).

count_of_elements_so_far = 0;
for (each element in linked list)
{
    search for current element in first <count_of_elements_so_far>
    if found, then you have a loop
    else,count_of_elements_so_far++;
}

Strathspey

How would you know how many elements are in the list to do the for()? – Kilter

@JethroLarson: The last node in a linked list points to a known address (in many implementations, this is NULL). Terminate the for-loop when that known address is reached. – Strathspey

Answer 10

public boolean hasLoop(Node start){   
   TreeSet<Node> set = new TreeSet<Node>();
   Node lookingAt = start;

   while (lookingAt.peek() != null){
       lookingAt = lookingAt.next;

       if (set.contains(lookingAt){
           return false;
        } else {
        set.put(lookingAt);
        }

        return true;
}   
// Inside our Node class:        
public Node peek(){
   return this.next;
}

Forgive me my ignorance (I'm still fairly new to Java and programming), but why wouldn't the above work?

I guess this doesn't solve the constant space issue... but it does at least get there in a reasonable time, correct? It will only take the space of the linked list plus the space of a set with n elements (where n is the number of elements in the linked list, or the number of elements until it reaches a loop). And for time, worst-case analysis, I think, would suggest O(nlog(n)). SortedSet look-ups for contains() are log(n) (check the javadoc, but I'm pretty sure TreeSet's underlying structure is TreeMap, whose in turn is a red-black tree), and in the worst case (no loops, or loop at very end), it will have to do n look-ups.

Mareld

Yes a solution with some kind of Set works fine, but requires space proportional to the size of the list. – Stickseed

Answer 11

If we're allowed to embed the class Node, I would solve the problem as I've implemented it below. hasLoop() runs in O(n) time, and takes only the space of counter. Does this seem like an appropriate solution? Or is there a way to do it without embedding Node? (Obviously, in a real implementation there would be more methods, like RemoveNode(Node n), etc.)

public class LinkedNodeList {
    Node first;
    Int count;

    LinkedNodeList(){
        first = null;
        count = 0;
    }

    LinkedNodeList(Node n){
        if (n.next != null){
            throw new error("must start with single node!");
        } else {
            first = n;
            count = 1;
        }
    }

    public void addNode(Node n){
        Node lookingAt = first;

        while(lookingAt.next != null){
            lookingAt = lookingAt.next;
        }

        lookingAt.next = n;
        count++;
    }

    public boolean hasLoop(){

        int counter = 0;
        Node lookingAt = first;

        while(lookingAt.next != null){
            counter++;
            if (count < counter){
                return false;
            } else {
               lookingAt = lookingAt.next;
            }
        }

        return true;

    }



    private class Node{
        Node next;
        ....
    }

}

Mareld

Answer 12

You could even do it in constant O(1) time (although it would not be very fast or efficient): There is a limited amount of nodes your computer's memory can hold, say N records. If you traverse more than N records, then you have a loop.

Howland

This is not O(1), this algorithm has no meaningful time complexity in big-O notation. The big-O-notation only tells you about the performance in the limit as the input size goes to infinity. So if your algorithm builds on the assumption that there are no lists with more than N elements for some large N, the limit of the runtime as the list size approaches infinity is undefined. Hence, the complexity is not "O(anything)". – Molloy

Answer 13

Detecting a loop in a linked list can be done in one of the simplest ways, which results in O(N) complexity using hashmap or O(NlogN) using a sort based approach.

As you traverse the list starting from head, create a sorted list of addresses. When you insert a new address, check if the address is already there in the sorted list, which takes O(logN) complexity.

Lemniscus

The complexity of this apporach is O(N log N) – Molloy

creating a sorted list with insertion will take O(log2n) to identify insertion point using binary search and for n insertions, will take O(nlog2(n)) worst case but insertion operation by itself can cause max n-1 shifts which is O(n). – Achromatism

So the insertion shifts of 'n' for each insertion point in 'n' insertions will cause Time Complexity of O(n^2) quadratic time irrespective of the search for insertion point which is O(log2(n)). – Achromatism

Creating a sorted array while inserting will have O(n*n) or O(n^2) Time Complexity. Instead of doing binary search O(log2(n)) to get the insertion point one could simply use linear search O(n) coz big-O still stands O(n^2) when using binary search due to the fact that max n shifts can take place. – Achromatism

@mahee96, O(NlogN) for sort and O(N logN) for binary search N times will result in O(NlogN) complexity – Lemniscus

@Lemniscus so you are saying that you will sort the addresses in one pass O(n) and then do lookups in 2nd pass so that it takes for n elements, log2n(binary search) time each leading to O(n*logn). If this the case the overall complexity is O(n) + O(nlogn) = O(nlogn). – Achromatism

@Lemniscus or if a balanced BST is used for searching, then at each insertion O(logn), the tree is already incrementally sorted, then a lookup O(logn) should add no cost to it, this for n elements time = O(n*(logn + logn)) = O(n*2logn) = O(nlogn). So yes it is feasible! – Achromatism

@Lemniscus Now Tree is an additional data structure, occupying O(n) space. If this were the case, then better algo would be to insert O(1) all into hashmap and do lookup O(1) whose time for n elements becomes O(n*1) = O(n) which is much better than using tree. – Achromatism

@Lemniscus On the other hand sort such as insertion, selection, bubble, merge, quick etc among whose least complexity is O(nlogn) and when inserting an item and performing sort to keep list sorted at each insertion so that lookup can be done using bin search O(logn), considering this for n elements we get O(nnlogn) + O(nlogn) = O(n^2 * logn) + O(nlogn) = O(n^2) complexity. – Achromatism

Answer 14

Here is my runnable code.

What I have done is to reveres the linked list by using three temporary nodes (space complexity O(1)) that keep track of the links.

The interesting fact about doing it is to help detect the cycle in the linked list because as you go forward, you don't expect to go back to the starting point (root node) and one of the temporary nodes should go to null unless you have a cycle which means it points to the root node.

The time complexity of this algorithm is O(n) and space complexity is O(1).

Here is the class node for the linked list:

public class LinkedNode{
    public LinkedNode next;
}

Here is the main code with a simple test case of three nodes that the last node pointing to the second node:

    public static boolean checkLoopInLinkedList(LinkedNode root){

        if (root == null || root.next == null) return false;

        LinkedNode current1 = root, current2 = root.next, current3 = root.next.next;
        root.next = null;
        current2.next = current1;

        while(current3 != null){
            if(current3 == root) return true;

            current1 = current2;
            current2 = current3;
            current3 = current3.next;

            current2.next = current1;
        }
        return false;
    }

Here is the a simple test case of three nodes that the last node pointing to the second node:

public class questions{
    public static void main(String [] args){

        LinkedNode n1 = new LinkedNode();
        LinkedNode n2 = new LinkedNode();
        LinkedNode n3 = new LinkedNode();
        n1.next = n2;
        n2.next = n3;
        n3.next = n2;

        System.out.print(checkLoopInLinkedList(n1));
    }
}

Wilden

Answer 15

 // To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
    Node slower, faster;
    slower = head;
    faster = head.next; // start faster one node ahead
    while (true) {

        // if the faster pointer encounters a NULL element
        if (faster == null || faster.next == null)
            return false;
        // if faster pointer ever equals slower or faster's next
        // pointer is ever equal to slower then it's a circular list
        else if (slower == faster || slower == faster.next)
            return true;
        else {
            // advance the pointers
            slower = slower.next;
            faster = faster.next.next;
        }
    }
}

Billen

Answer 16

boolean hasCycle(Node head) {

    boolean dec = false;
    Node first = head;
    Node sec = head;
    while(first != null && sec != null)
    {
        first = first.next;
        sec = sec.next.next;
        if(first == sec )
        {
            dec = true;
            break;
        }

    }
        return dec;
}

Use above function to detect a loop in linkedlist in java.

Poulson

Almost the same as my answer above, but has an issue. It will throw a NullPointerException for lists with odd length lists (without loops). For example, if head.next is null, then sec.next.next will throw a NPE. – Rotifer

Answer 17

I cannot see any way of making this take a fixed amount of time or space, both will increase with the size of the list.

I would make use of an IdentityHashMap (given that there is not yet an IdentityHashSet) and store each Node into the map. Before a node is stored you would call containsKey on it. If the Node already exists you have a cycle.

ItentityHashMap uses == instead of .equals so that you are checking where the object is in memory rather than if it has the same contents.

Geneticist

It's certainly impossible for it to take a fixed amount of time, as there could be a loop at the very end of the list, so the entire list must be visited. However, the Fast/Slow algorithm demonstrates a solution using a fixed amount of memory. – Rotifer

Is it not referring to it's asymptotic behaviour, i.e it is linear O(n) where n is the length of the list. Fixed would be O(1) – Regelation

Answer 18

I might be terribly late and new to handle this thread. But still..

Why cant the address of the node and the "next" node pointed be stored in a table

If we could tabulate this way

node present: (present node addr) (next node address)

node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)

Hence there is a cycle formed.

Feme

Your solution does not pass the "constant amount of space" requirement. – Claraclarabella

Answer 19

This approach has space overhead, but a simpler implementation:

Loop can be identified by storing nodes in a Map. And before putting the node; check if node already exists. If node already exists in the map then it means that Linked List has loop.

public boolean loopDetector(Node<E> first) {  
       Node<E> t = first;  
       Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();  
       while (t != null) {  
            if (map.containsKey(t)) {  
                 System.out.println(" duplicate Node is --" + t  
                           + " having value :" + t.data);  

                 return true;  
            } else {  
                 map.put(t, t);  
            }  
            t = t.next;  
       }  
       return false;  
  }  

Thedathedric

This does not meet the constant amount of space restriction given in the question! – Aram

agree it has space overhead; it's another approach to solve this problem. The obvious approach is tortoise and harse algorithm. – Thedathedric

@downvoter, it would be helpful if you could explain the reason as well. – Thedathedric

Answer 20

This code is optimized and will produce result faster than with the one chosen as the best answer.This code saves from going into a very long process of chasing the forward and backward node pointer which will occur in the following case if we follow the 'best answer' method.Look through the dry run of the following and you will realize what I am trying to say.Then look at the problem through the given method below and measure the no. of steps taken to find the answer.

1->2->9->3 ^--------^

Here is the code:

boolean loop(node *head)
{
 node *back=head;
 node *front=head;

 while(front && front->next)
 {
  front=front->next->next;
  if(back==front)
  return true;
  else
  back=back->next;
 }
return false
}

Creigh

Are you sure that this produces the right result in all situations ? If you run this algorithm on the list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 3 -> ..., I believe that it would return 4 as the head, whereas you wanted 3. – Limassol

The question is just finding if there exists a loop or not.In this case,yes,the question will absolutely work fine and get the desired boolean result for the case.If you want the exact node from where the loop started,then we will need to add somethng more to the code.But as far as producing a result is concerned,this willl produce a faster conclusion. – Creigh

You didn't read the question properly : What's the best way of writing boolean hasLoop(Node first) which would return true if the given Node is the first of a list with a loop, and false otherwise? – Limassol

Here is the dry run for your list.First value means back pointer and second part means forward pointer.(1,1)-(1,3)-(2,3)-(2,5)-(3,5)-(3,7)-(4,7)-(4,4). – Creigh

Actually, I realize now that there are two ways to understand the question (or at least I see two different interpretations). Your algorithm is correct if you're just searching if there's a loop. But I thought that the question was asking where the loop was starting. – Limassol

To find loop,once we find the back and forward matching positions,we can keep the back node fixed and start increasing the forward pointer by 1, while counting each step in a int variable.Once both the pointers match again,we know the size of the loop.Now we start the back node from head and forward node at 'n' steps ahead of the head node,where n is the size of loop calculated above.We keep increasing both the nodes by 1 till they match each other.In this case,the matching positions will surely be the start of the loop.The complexity is O(n) however. – Creigh

Answer 21

Here is my solution in java

boolean detectLoop(Node head){
    Node fastRunner = head;
    Node slowRunner = head;
    while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
        fastRunner = fastRunner.next.next;
        slowRunner = slowRunner.next;
        if(fastRunner == slowRunner){
            return true;
        }
    }
    return false;
}

Magnetic

Answer 22

You may use Floyd's tortoise algorithm as suggested in above answers as well.

This algorithm can check if a singly linked list has a closed cycle. This can be achieved by iterating a list with two pointers that will move in different speed. In this way, if there is a cycle the two pointers will meet at some point in the future.

Please feel free to check out my blog post on the linked lists data structure, where I also included a code snippet with an implementation of the above-mentioned algorithm in java language.

Regards,

Andreas (@xnorcode)

Carolanncarole

Answer 23

Here is the solution for detecting the cycle.

public boolean hasCycle(ListNode head) {
            ListNode slow =head;
            ListNode fast =head;

            while(fast!=null && fast.next!=null){
                slow = slow.next; // slow pointer only one hop
                fast = fast.next.next; // fast pointer two hops 

                if(slow == fast)    return true; // retrun true if fast meet slow pointer
            }

            return false; // return false if fast pointer stop at end 
        }

Deryl

Answer 24

// linked list find loop function

int findLoop(struct Node* head)
{
    struct Node* slow = head, *fast = head;
    while(slow && fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return 1;
    }
 return 0;
}

Solstice

Answer 25

If the linked list structure implements java.util.List. We can use the list size to keep track of our position in the list.

We can traverse the nodes comparing our current position to the last node's position. If our current position surpasses the last position, we've detected the list has a loop somewhere.

This solution takes a constant amount of space, but comes with a penalty of linearly increasing the amount of time to complete as list size increases.

class LinkedList implements List {
    Node first;
    int listSize;
    
    @Override
    int size() {
        return listSize;
    }

    [..]

    boolean hasLoop() {
        int lastPosition = size();
        int currentPosition = 1;
        Node next = first;
        while(next != null) {
           if (currentPosition > lastPosition) return true;
           next = next.next;
           currentPosition++;
        }
        return false;
    }
}

Or as a utility:

static boolean hasLoop(int size, Node first) {
    int lastPosition = size;
    int currentPosition = 1;
    Node next = first;
    while(next != null) {
       if (currentPosition > lastPosition) return true;
       next = next.next;
       currentPosition++;
    }
    return false;
}

Kira

Answer 26

I'm not sure whether this answer is applicable to Java, however I still think it belongs here:

Whenever we are working with pointers on modern architectures we can expect them to be CPU word aligned. And for a 64 bit architecture it means that first 3 bits in a pointer are always zero. Which lets us use this memory for marking pointers we have already seen by writing 1 to their first bits.

And if we encounter a pointer with 1 already written to its first bit, then we've successfully found a loop, after that we would need to traverse the structure again and mask those bits out. Done!

This approach is called pointer tagging and it is used excessively in low level programming, for example Haskell uses it for some optimizations.

Beira

Answer 27

func checkLoop(_ head: LinkedList) -> Bool {
    var curr = head
    var prev = head
    
    while curr.next != nil, curr.next!.next != nil {
        curr = (curr.next?.next)!
        prev = prev.next!
        
        if curr === prev {
            return true
        }
    }
    
    return false
}

Defilade

Answer 28

I read through some answers and people have missed one obvious solution to the above problem.

If given we can change the structure of the class Node then we can add a boolean flag to know if it has been visited or not. This way we only traverse list once.

Class Node{

 Data data;
 Node next;
 boolean isVisited;

}


public boolean hasLoop(Node head){
   
     if(head == null) return false;

     Node current = head;


     while(current != null){
      if(current.isVisited) return true;
      current.isVisited = true;
      current = current.next;
     }

    return false;

}

Effusive

Answer 29

public boolean isCircular() {

    if (head == null)
        return false;

    Node temp1 = head;
    Node temp2 = head;

    try {
        while (temp2.next != null) {

            temp2 = temp2.next.next.next;
            temp1 = temp1.next;

            if (temp1 == temp2 || temp1 == temp2.next) 
                return true;    

        }
    } catch (NullPointerException ex) {
        return false;

    }

    return false;

}

Richardo