Got accepted O(n) solution using same concept from finding the Lowest Common Ancestor of a Binary Tree Part II


  • 0
    L
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        int height(ListNode *head)
        {
            ListNode *p1 = head;
            int height = 0;
            if (p1 == NULL)
            return height;
            else
            {
                while (p1)
                {
                    height+=1;
                    p1 = p1->next;
                }
            }
            return height;
        }
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            ListNode *p1 = headA;
            ListNode *p2 = headB;
            int h1 = height(p1);
            int h2 = height(p2);
            if (h1 == 0 && h2 == 0)
            return NULL;
            if ( h1 > h2)
            {
                swap(h1,h2);
                swap(p1,p2);
            }
            int dh = h2 - h1;
            for (int i = 0; i < dh; i++)
            p2 = p2->next;
            while(p1!= NULL && p2 != NULL)
            {
                if (p1 == p2)
                    return p1;
                p1 = p1->next;
                p2 = p2->next;
            }
            return NULL;
        }
    };

Log in to reply
 

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