Finding loop in linked list complexity?

Question

The normal scenario to find the loop in the linked list is to move a pointer once and move other pointer two times.If they meet,there is a loop in the linked list.

But what will happen if i move the second pointer three times or four times.Will it reduce the complexity?Why we need to move second pointer two times only.

boolean hasLoop(Node first) {
    Node slow, fast; 
    slow = fast = first; 
    while(true) {
        slow = slow.next; 
        if(fast.next != null)
            fast = fast.next.next; 
        else
            return false;  

        if(slow == null || fast == null) 
            return false;

        if(slow == fast) 
            return true;
    }
}

Instead of fast.next.next,why cant i have fast.next.next.next or fast.next.next.next.next.next?

I don't follow the question, can you show in code what you mean? Do you wish to find possible loops in a singly linked list (where all nodes have pointers to subsequent nodes only)? There are some different strategies for that, converting it to a doubly linked list, is an option there, as the keeping of a backlink will make it rudimentary to find loops... If you traverse it from the front, and find a node where the backlink is NOT the link you just came from, then you can assume two nodes link to the same thing. Regarding moving pointers, as i said, please show code... — Richard Tyregrim
– Richard Tyregrim, Commented Nov 26, 2015 at 11:56
@RichardEriksson I think this is an understanding question, rather than an implementation question - so why would it be impractical to speed up the faster pointer? — Verzweifler
– Verzweifler, Commented Nov 26, 2015 at 12:02

Manisha · Accepted Answer · 2015-11-26 18:50:09Z

Since fast pointer is moving at double speed than slow, therefore distance between the two pointers will always increase by 1 (initially the distance between them was 2).

Now assume that loop exists and when slow pointer entered the loop, distance between slow and fast was say "x" and the length of the loop is "d". So now the next time slow and fast will move, distance between them will become x+1 and after that on next move it will be x+2, then x+3 and so on. Fast and slow will meet whenever the distance between them will be a multiple of d. So by increasing distance between them by 1 we are checking at every value.

Now consider the case when fast is moving three times faster, then at each step distance between them will increase by 2 i.e x, x+2, x+4 and so on. So the two pointers might not meet each other and cross each other and if that happens your program will never terminate. Similar is the case if speed of fast pointer is four times, five times etc.

Verzweifler · Accepted Answer · 2015-11-26 12:08:52Z

1

With the faster pointer moving with more than double the speed of the slower pointer, it can overlap the first pointer without meeting it. If this happens every time the two pointers pass (inside the same loop), the algorithm would 1. never find the loop and 2. never terminate.

answered Nov 26, 2015 at 12:08

Verzweifler

9406 silver badges19 bronze badges

Comments

Joop Eggen · Accepted Answer · 2015-11-26 12:37:17Z

Complexity is not counted by the number of loop steps, but the nodes visited. Hence the above algorithm just makes preventing NullPointerExceptions more difficult. Also cycles can be any length of nodes.

A quadratic algorithm would be needed in the naive solution: checking that node[i] did not occur as node[j] for all j < i.

A faster algorith uses memory.

Either by a generation marker (a kind of reference count) as field of the node.

// Complexity O(N)

class Node
    Node next;
    boolean generation;

class List
    Node first;
    boolean nodesGeneration; // All nodes false or true

    boolean isCircular() {
        for (Node node = first; node != null; node = node.next) {
            if (node.generation != nodesGeneration) {
                return false;
            }
            node.generation = !node.generation;
        }
        nodesGeneration = !nodesGeneration;
        return true;
    }

Or if this is not possible/desired: use an IdentityHashMap that takes the Object reference as key. Like a set of object references (==).

// Complexity O(N), worse case O(N . log N)

    boolean isCircular() {
        Map<Node, Boolean> checkedNodes = new IdentityHashMap<>();
        for (Node node = first; node != null; node = node.next) {
            if (checkedNodes.containsKey(node)) {
                return false;
            }
            checkedNodes.put(node, Boolean.TRUE);
        }
        return true;
    }

Collectives™ on Stack Overflow

Finding loop in linked list complexity?

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related