java - Cracking the Coding Interview Circular Linked List -

the question: given circular linked list, implement algorithm returns node @ beginning of loop.

definition: circular linked list: (corrupt) linked list in node's next pointer points earlier node, make loop in linked list.

example: input: -> b -> c -> d -> e -> c[the same c earlier] output: c

my solution keep track of nodes seen inside arraylist , once node have seen, know node @ beginning of 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 use fast pointer , slow pointer. solution better?

thank you.

in terms of space complexity, yes solution better. solution requires maintain nodes have been seen, o(n), n being size of list.