C++ with detailed comments


  • 0
    B
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
        {
            if(!headA || !headB) return NULL;
            
            //find length of two list
            int countA=1, countB=1;
            ListNode * probeA = headA;
            ListNode * probeB = headB;
            while(probeA->next)
            {
                countA++;
                probeA = probeA -> next;
            }
            
            while(probeB->next)
            {
                countB++;
                probeB = probeB -> next;
            }
            
            //return NULL if they do not have same rear node
            if(probeA != probeB) return NULL;
            
            //move head to have same length
            if(countA>countB)
            {
                while(countA>countB)
                {
                    headA = headA->next;
                    countA--;
                }
            }
            else
            {
                while(countA<countB)
                {
                    headB = headB -> next;
                    countB--;
                }
            }
            //both heads move toward intersection
            while(headA != headB)
            {
                headA = headA -> next;
                headB = headB -> next;
            }
            return headA;
        }
    };

Log in to reply
 

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