Making a loop in the list to find the intersection. (Intersection of Two Lists problem).


  • 0
    K

    I first make the last node in list A to the head Node of list B. After the the problem is reduced to finding starting of the loop in a linked list. Here's the code:

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if(headA == NULL || headB == NULL)         return NULL;
            ListNode* currA = headA;
            while(currA-> next != NULL)     currA = currA-> next;
            currA-> next = headB;
            ListNode *toDelete = currA;
            ListNode *slowPtr = headA, *fastPtr = headA-> next;
            while(slowPtr != fastPtr) {
                if(slowPtr == NULL || fastPtr == NULL || fastPtr-> next == NULL) {
                    toDelete-> next = NULL;               /* no intersection found */
                    return NULL;
                }
                slowPtr = slowPtr-> next;
                fastPtr = fastPtr-> next-> next;
            }
                                                          /*calculate the length of loop */
            fastPtr = fastPtr-> next;
            int loopSize = 1;
            while(fastPtr != slowPtr){
                fastPtr = fastPtr-> next;
                loopSize++;
            }                                             /* find the starting of the loop */
            slowPtr = headA;
            fastPtr = headA;
            for(int i=0; i<loopSize; fastPtr = fastPtr-> next, i++);
            while(fastPtr != slowPtr) {
                fastPtr = fastPtr-> next;
                slowPtr = slowPtr-> next;
            }
            toDelete-> next = NULL;
            return fastPtr;
        }

Log in to reply
 

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