Problem

Write a program to find the node at which the intersection of two singly linked lists begins.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Example

For example, the following two linked lists:

A:          a1 → a2
                  ↘
                    c1 → c2 → c3
                  ↗            
B:     b1 → b2 → b3

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
static int var = [](){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB)
            return NULL;
        ListNode *tempA = headA;
        ListNode *tempB = headB;
        int difflen = getDiffLength(tempA,tempB);
        tempA=headA;
        tempB=headB;
        if(difflen>0){
            while(difflen--){
                tempB=tempB->next;
            }
        }else if(difflen<0){
            while(difflen++){
                tempA=tempA->next;
            }
        }
        while(tempA!=tempB){
            tempA=tempA->next;
            tempB=tempB->next;
        }
        return  tempA;
    }
    int getDiffLength(ListNode *tempA,ListNode *tempB){
        int difflen = 0;
        while(tempA && tempB){
            tempA=tempA->next;
            tempB=tempB->next;
        }
        if(!tempA && !tempB)
            return 0;
        if(!tempA){
            while(tempB){
                difflen++;
                tempB=tempB->next;
            }
        }else{
            while(tempA){
                difflen--;
                tempA=tempA->next;
            }
        }
        return difflen;
    }
};

Result

160. Intersection of Two Linked Lists.png