google-code-prettify

Sunday, 2 December 2012

Cycle in LinkedList

There is an interesting technique how you can verify if there is a cycle in a LinkedList without using any additional data structure. All that is needed are two references (fast runner and slow runner) of the same type as the elements in the linked list. Here is the solution:
boolean hasCycle(Node linkedList) {
    if (linkedList == null) {
        return false;
    }
    Node n1, n2;
    n1 = linkedList;
    n2 = linkedList.getNext();
    while (n1 != null && n2 != null) {
        if (n1.equals(n2)) {
            return true;
        }

        n1 = n1.getNext();
        if (n2.getNext() != null) {
            n2 = n2.getNext().getNext();
        } else {
            return false;
        }

    }
    return true;
}

No comments:

Post a Comment