Linked List - Reverse & identifying the cycle

Linked List- another interesting and simple data structure. Most of the interviewers ask for reverse and identifying the cycle in linked list.

Identifying the cycle
Traversal of a linked list with a cycle will never end, so there needs to be some method to keep track of what nodes have been encountered.


One idea is to mark nodes that have been seen, either by adding a flag to the node itself or storing information about the node in a separate data structure. Unfortunately, this method requires modification of the node and/or additional space.


Interviewers won't accept this way as they want to understand/see how we traverse across nodes.

Another idea is to move the pointers in different speed to identify a cycle as below. To make one pointer faster than the other, just advance it two nodes instead of one.

public static boolean hasCycle(Node head) {

Node fast = head;
Node slow = head;

while (true) {
if (fast == null || fast.next == null)
return false;
else if (fast == slow || fast.next == slow)
return true;
else {
fast = fast.next.next;
slow = slow.next;
}
}
}
Reverse


With three pointers, reverse will be pretty straight forward to move on.



Node previous = null;
Node current = head;
Node forward;

while (current != null) {
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}

Download the code (Just copy & paster in your editor)