| 5 | public class Question { |
| 6 | |
| 7 | public static LinkedListNode FindBeginning(LinkedListNode head) { |
| 8 | LinkedListNode slow = head; |
| 9 | LinkedListNode fast = head; |
| 10 | |
| 11 | // Find meeting point |
| 12 | while (fast != null && fast.next != null) { |
| 13 | slow = slow.next; |
| 14 | fast = fast.next.next; |
| 15 | if (slow == fast) { |
| 16 | break; |
| 17 | } |
| 18 | } |
| 19 | |
| 20 | // Error check - there is no meeting point, and therefore no loop |
| 21 | if (fast == null || fast.next == null) { |
| 22 | return null; |
| 23 | } |
| 24 | |
| 25 | /* Move slow to Head. Keep fast at Meeting Point. Each are k steps |
| 26 | /* from the Loop Start. If they move at the same pace, they must |
| 27 | * meet at Loop Start. */ |
| 28 | slow = head; |
| 29 | while (slow != fast) { |
| 30 | slow = slow.next; |
| 31 | fast = fast.next; |
| 32 | } |
| 33 | |
| 34 | // Both now point to the start of the loop. |
| 35 | return fast; |
| 36 | } |
| 37 | |
| 38 | public static void main(String[] args) { |
| 39 | int list_length = 100; |