Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created July 15, 2016 00:29
Show Gist options
  • Save jianminchen/3b7194dd0f2e3672542046bda3d95d66 to your computer and use it in GitHub Desktop.
Save jianminchen/3b7194dd0f2e3672542046bda3d95d66 to your computer and use it in GitHub Desktop.
Linked List Cycle - facebook code lab - pass all test cases - no nested while loop
/**
* Definition for singly-linked list.
* class ListNode {
* public int val;
* public ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
public class Solution {
/*
1. if there is no cycle, return null
2. if there is a cycle, use two runner, meet a same node;
and then, third runner starts from begining to meet the normal
runner at the beginning of cycle.
study the code:
https://siddontang.gitbooks.io/leetcode-solution/content/linked_list/linked_list_cycle.html
*/
public ListNode detectCycle(ListNode a) {
if(a == null || a.next == null) {
return null;
}
ListNode fast = a;
ListNode slow = a;
boolean foundLoop = false;
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
foundLoop = true;
break;
}
}
if(!foundLoop)
return null;
// stil use fast slow two pointers, but need to move one step
slow = a;
while(slow != fast)
{
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment