Q:

Cracking the Coding Interview Circular Linked List

The question:
Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
Definition: Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
Example:
Input: A -> B -> C -> D -> E -> C[the same C as earlier]
Output: C
My solution is to keep track of which nodes are seen inside an ArrayList and then once I get to a node that I have already seen, then I know that is the node at the beginning of the loop.
findBeginningLoop function:
public Node findBeginningLoop(Node n) {
    ArrayList<Node> nodes = new ArrayList<Node>();
    Node pointer = n;
    while (true) {
        Node checkingNode = pointer;
        if (!nodes.contains(checkingNode)) {
            nodes.add(checkingNode);
        } else {
            return checkingNode;
        }
    }
}

Node class:
public class Node {
    Node next = null;
    int val;

    public Node(int d) {
        val = d;
    }

    public void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }   
}

Her solution is to use a fast pointer and slow pointer. Is that solution much better?

A:

In terms of space complexity, yes her solution is obviously better. Your solution requires you to maintain all nodes that have already been seen, which is O(n), n being the size of the list.

