java solution


  • 0
    M
    public class Solution {
      public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        
        // no cycle
        if (fast.next == null || fast.next.next == null) {
            return null;
        }
        
        // cycle exist
        slow = head;    // one pointer start at head
        
        ListNode anotherHead = fast.next;
        fast.next = null;   // break the cycle
        fast = anotherHead; // one pointer start at another head
        
        // to check if slow and fast will meet at the first connected node, now the shape is like "Y"
        while (slow != fast) {
            slow = slow.next == null? anotherHead : slow.next;
            fast = fast.next == null? head : fast.next;
        }
        return fast;
      }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.