My C solution(36ms), transforming it to finding start of the loop using the Floyd's algorithm


  • 0
    R
    struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
        // Initials
        if (headA == NULL || headB == NULL ) return NULL;
        if (headA == headB) return headA;
        if(headA->next == NULL && headB->next == NULL && headA != headB)return NULL;
    
    
    	struct ListNode *slow = headB;
    	struct ListNode *fast = headB;
    	struct ListNode *end = headB;
    	while (slow->next != NULL){
    	    slow = slow->next;
    	}
    	fast = slow;
    	end = slow; // Mark the end
    	end->next = headA; // Points the end to headA to make a loop
    
        // Floyd's Algorithm
    	while(slow->next!=NULL){
    	    slow = slow->next;
    	    if(slow == fast){
    	        slow = headB;
    	        fast = headB;
    	        while ( fast && fast->next )  {
                    slow = slow->next;
                    fast = fast->next->next;
                    if ( slow == fast ) break;
                }
                if (fast == NULL || fast->next == NULL) return NULL;
                slow = headB;
                while (slow != fast) {
                     slow = slow->next;
                     fast = fast->next;
                }
                end->next = NULL; // Restore the two list 
                return slow; // The start of the loop is the intersection
    	    }
    	}
    	end->next = NULL; // Restore the two list 
    	return NULL;
    }

Log in to reply
 

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