Created
June 27, 2014 00:16
-
-
Save JoyceeLee/8358b4b671949731cc42 to your computer and use it in GitHub Desktop.
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
/*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 | |
*/ | |
public class Solution { | |
public ListNode findNOde(ListNode head) { | |
ListNode slow = head; | |
ListNode fast = head; | |
while(true) { | |
fast = fast.next.next; | |
slow = slow.next; | |
if(fast==slow) break; | |
} | |
slow = head; | |
while(fast!=slow) { | |
fast = fast.next; | |
slow = slow.next; | |
} | |
return slow; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment