Share my O(n) time complexity, constant space method based on Linked List Cycle


  • 3
    W

    The main idea is:

    1. Scan the list A and store the last node to be endA
    2. Let the the next of the endA points to the head of the list B
    3. Find the loop position of the new list headA
    4. Don't forget to keep the original of the list A

    The code is below and any comment is welcomed!

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    	if (headA == nullptr || headB == nullptr) {
    		return nullptr;
    	}
    	ListNode *endA = headA;
    	while (endA->next != nullptr) {
    		endA = endA->next;
    	}
    	// Let the tail of the A points to the head of B
    	endA->next = headB;
    
    	ListNode *slow = headA, *fast = headA;
    	while (fast->next != nullptr && fast->next->next != nullptr) {
    		slow = slow->next;
    		fast = fast->next->next;
    		if (slow == fast) {
    			fast = headA;
    			while (fast != slow) {
    				fast = fast->next;
    				slow = slow->next;
    			}
    			// Keep the original Linked List
    			endA->next = nullptr;
    			return slow;
    		}
    	}
    	// Keep the original Linked List
    	endA->next = nullptr;
    	return nullptr;
    }

  • 0
    Y

    It's a smart method! If you are puzzled about it, you can read my analysis~

    Assuming that:

                       S1 = the distance between headA and the intersection 
    
                         T = the circle's length                  (S1 + T = all nodes)
    

    And:

                       S1 = n*T + delta (int n)
    

    what we know is 'slow''s speed is 1, 'fast''s speed is 2

    1-Now we start from headA------

    Before slow == fast ,we need to run
    [S1/T]*T + T = (S1 + T - delta) step.

    2-Then we set 'fast' = headA .( and set fast's speed to 1)

    It means that--now the distance between 'slow' and 'fast' = n*T

    3-After another n*T step, slow and fast arrive the intersection!

    So, totoaly we move about 2*S1 + T step.
    Time complexity is O(n)!


  • 0
    W

    Thx! I exactly used a lot time on this math work!


Log in to reply
 

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