Skip to content

Instantly share code, notes, and snippets.

@nealhu
Created June 30, 2014 03:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nealhu/e333fc1162464261f663 to your computer and use it in GitHub Desktop.
Save nealhu/e333fc1162464261f663 to your computer and use it in GitHub Desktop.
CC_2_6
// Cracking the Coding Interview
// 2.6
// 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[thesameCasearlier]
// Output:C
class Node {
public Node next;
public int val;
Node(int _v) {
val = _v;
next = null;
}
}
class LoopInLinkedList {
public static Node detectLoop(Node head) {
Node slow = head;
Node fast = head;
boolean met = false;
boolean firstTime = true;
while (slow != null && fast != null && fast.next != null) {
if (firstTime) {
firstTime = false;
} else {
if (slow == fast) {
met = true;
break;
}
}
slow = slow.next;
fast = fast.next.next;
}
if (!met) return null;
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
public static void main(String[] args) {
Node test1 = arrayToLinkedList(new int[]{1, 2, 3, 4});
Node test2 = arrayToLinkedList(new int[]{1, 2, 3, 4});
test2.next.next.next.next = test2;
Node test3 = arrayToLinkedList(new int[]{1, 2, 3, 4});
test3.next.next.next.next = test3.next;
Node test4 = arrayToLinkedList(new int[]{1, 2, 3, 4});
test4.next.next.next.next = test4.next.next.next;
Node test5 = arrayToLinkedList(new int[]{1});
Node test6 = arrayToLinkedList(new int[]{1});
test6.next = test6;
assert detectLoop(test1) == null;
assert detectLoop(test2) == test2;
assert detectLoop(test3) == test3.next;
assert detectLoop(test4) == test4.next.next.next.next;
assert detectLoop(test5) == null;
assert detectLoop(test6) == test6;
System.out.println("Tests Passed");
}
private static Node arrayToLinkedList(int[] arr) {
if (arr == null || arr.length < 1) return null;
Node fakeHead = new Node(0);
Node cur = fakeHead;
for(int i = 0; i < arr.length; i++) {
cur.next = new Node(arr[i]);
cur = cur.next;
}
return fakeHead.next;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment