A different solution : modify the integer value of the node


  • 2

    Just another way to do it, not very efficient.

    The basic idea is that we can use the integer values held by nodes to do the job. For listA, we can increment the value of each node by 1. For listB, we do the opposite, decrement the value of each node by 1. Of course, we need to calculate the sum of listA before and after. Now we compare the pre-sum and after-sum, if the difference is the size of listA, that means there is no intersection. Otherwise there is an intersection, and we also know the sequence number of the node from the head of listA.

    The modification and recovery of nodes is rather tedious.

    class Solution {
        public:
            ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
                if( !headA || !headB ) return NULL;
                ListNode* pA = headA, *pB = headB, *ans = NULL;
                int szA = 0, szB = 0, preSUM = 0, SUM = 0;
                while( pA ) {
                    szA++;
                    preSUM += pA->val;
                    pA->val++;
                    pA = pA->next;
                }
                while( pB ) {
                    szB++;
                    pB->val--;
                    pB = pB->next;
                }
                pA = headA;
                while( pA ) {
                    SUM += pA->val;
                    pA = pA->next;
                }
                int n = SUM - preSUM;
                ans = headA;
                while( n-- && ans ) {
                    ans->val--;
                    ans = ans->next;
                }
                pB = headB;
                while( pB && pB != ans ) {
                    pB->val++;
                    pB = pB->next;
                }
                return ans;
            }
    };

Log in to reply
 

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