A solution with two pointers


  • 1
    S

    the basic idea:
    (1) first get the crossing node X when a fast and slow pointer came across
    (2) start from X and head, then the crossing node Y is the cycle begins

    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return NULL;
        ListNode *slow = head->next;
        ListNode *fast = head->next->next;
        
        // slow and fast pointers run continuously
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) break;
        }
        
        if (slow != fast) return NULL;
        
        // the second crossing node is the cycle begins 
        while (slow != head) {
            slow = slow->next;
            head = head->next;
        }
        
        return head;
    }

  • 0
    D

    The same idea in Java:

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if(head == null || head.next == null) return null;
            ListNode slow = head.next;
            ListNode fast = slow.next;
            
            while(slow!=null && fast!=null){
                if(fast.next == null || slow == fast) break;
                slow = slow.next;
                fast = fast.next.next;
            }
            
            if(slow == null || fast == null || fast.next == null) return null;
            while(true){
                if(head == slow) return slow;
                head = head.next;
                slow = slow.next;
            }
        }
    }
    

  • 0
    K

    How can we be sure about whether they will meet the second time ?


  • 0
    K

    Well , i get that , sorry for bothering :)


Log in to reply
 

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