Concise 48ms C++ solution with description and comment on trees


  • 18
    D

    The idea is to first fast forward each pointer to the end to find their distances from the end. Then we can fast forward the farther pointer so they're the same distance from the end. Finally we can fast forward both at the same time until they coincide.

    This same exact approach can also be used to find the least common ancestor (LCA) of two nodes in a tree where nodes have parent pointers.

    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            
            auto currA = headA, currB = headB;
            int countA = 0, countB = 0;
            
            while (currA) { 
                currA = currA->next, countA++;
            }
            while (currB) {
                currB = currB->next, countB++;
            }
            int diff = std::abs(countA - countB);
            if (countB > countA) { swap(headA, headB); }
            while (diff--) { 
                headA = headA->next;
            }
            while (headA != headB) {
                headA = headA->next, headB = headB->next;
            }
            return headA;
        }
    };

  • 0
    T

    niubility~~~~


  • 0
    Q

    smart idea, jump the different amount of node, and then move&compare.
    Niubility~~~


  • 0
    Q

    What if the following?
    A: 1->2->6->7->8
    B: 3->4->5->6->7->9


  • 0
    Z

    Really smart and non-tricky solution!
    Vote for you


  • 0
    B

    I think the result from this solution is wrong under your case


  • 0
    K
    int getnodenum(ListNode *head)
    {
    	int num = 0;
    	ListNode *p = head;
    	while (p)
    	{
    		num++;
    		p = p->next;
    	}
    
    	return num;
    }
    
    ListNode *findnode(ListNode *head1, ListNode *head2, int n1, int n2)
    {
    
    	ListNode *p1 = head1;
    	ListNode *p2 = head2;
    
    	for (int i = 0; i < n1 - n2; i++)
    	{
    		p1 = p1->next;
    	}
    
    	for (int i = 0; i < n2; i++)
    	{
    		if (p1 == p2)
    			return p1;
    		else
    		{
    			p1 = p1->next;
    			p2 = p2->next;
    		}
    	}
    
    	return NULL;
    }
    
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    	if (!headA || !headB) return NULL;
    
    	ListNode *p1 = headA;
    	ListNode *p2 = headB;
    
    	int numA = getnodenum(p1);
    	int numB = getnodenum(p2);
    
    	if (numA >= numB)
    	{
    		return findnode(p1, p2, numA, numB);		
    	}
    
    	if (numB > numA)
    	{
    		return findnode(p2, p1, numB, numA);
    	}
    
    }

Log in to reply
 

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