-2

There might be a loop within a linked list, how to determine where the loop happens within a linked list.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
user1330526
  • 151
  • 1
  • 3
  • 10

2 Answers2

5

If there's a loop, it's no longer a linked list. It's a directed graph. The loop is called a cycle.

One way to find a cycle in a graph is by iterating through the list, marking each item. If you find an item already marked, you've found a cycle.

Andy Thomas
  • 84,978
  • 11
  • 107
  • 151
2

You can tell if there's a loop in a linked list by saving a reference to a node (say, the one at the head of the list) and start iterating over the list. If at some point you reach the end of the list (a null value), then there isn't a loop. But if you happen to find again the same node that was previously saved, then you know that the list is circular. Either way, stop iterating.

For example, in Java this method will tell you if a linked list of Nodes is circular:

public boolean isCircular(Node list) {
    Node current = list;
    while (current != null) {
        if (current.next == list)
            return true;
        current = current.next;
    }
    return false;
}

EDIT :

For the general solution for finding an arbitrary loop in a linked list, read about the Floyd's cycle-finding algorithm (a.k.a. "the tortoise and the hare" algorithm). There's a fine Java implementation in this previous post.

Community
  • 1
  • 1
Óscar López
  • 232,561
  • 37
  • 312
  • 386
  • This does not detect loops formed between arbitrary points though (eg node 6 looping back to node 4). You will have to call this same method for every node in the list which is difficult considering that you cant safely iterate over it. – Numeron May 10 '12 at 02:56
  • @Numeron You're right. For that, it'd be necessary to store all the visited nodes in a separate data structure (a set, for instance) and for each node traversed, see if it was visited already . – Óscar López May 10 '12 at 02:58