A C# 6-Line Solution


  • 2
    L
    public ListNode DetectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode p1 = head.next;
        for(ListNode p2 = head.next.next; p1 != p2 || p2 == null; p1 = p1.next, p2 = p2.next.next)
            if(p2 == null || p2.next == null) return null;
        for(ListNode p2 = head; ; p1 = p1.next, p2 = p2.next) if(p1 == p2) return p1;
        return null;
    }

  • 1
    L

    CPP code with explanation based on lestrois's solution.

    // slow: 1 nodes/sec
    // fast: 2 nodes/sec
    //
    // The cycle has M nodes. At time t0, the slow is the first node in the cycle,
    // the fast is the n node. t0 % M  == n
    // After t seconds, slow and fast meet. t % M == (2t + n) % M
    // t + k*M == 2t + n
    // t = k * M - n
    // k == 1 is the frist meet. At this time, t = M - n;
    // So the first time slow and fast meet, slow has not scaned the cycle one time.
    //
    // t0 = x * M + n
    //
    
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
    	if (NULL == head || NULL == head->next)
    		return NULL;
    
    	// Reverse head
    	ListNode *slow = head;
    	ListNode *fast = head->next;
    
    	while (slow != fast) {
    		if (NULL == slow->next)
    			return NULL;
    		if (NULL == fast->next || NULL == fast->next->next)
    			return NULL;
    		slow = slow->next;
    		fast = fast->next->next;
    	}
    
    	ListNode *node = head;
    	ListNode *cycle_node = slow->next;
    
    	// It takes t0 seconds from head to the first node of the cycle
    	// t0 = x * M + n
    	// It needs n seconds from meet to the first node of the cycle
    	// So node and cycle_node will meet at the first node of the cycle
    	while (node != cycle_node) {
    		node = node->next;
    		cycle_node = cycle_node->next;
    	}
    
    	return node;
        }
    };

Log in to reply
 

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