Created
June 30, 2014 03:07
-
-
Save nealhu/e333fc1162464261f663 to your computer and use it in GitHub Desktop.
CC_2_6
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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