C++: Intersection of Two Linked Lists

Thought Process

To find the intersection node of two linked lists, we use a two-pointer technique. We initialize two pointers, 'a' and 'b', at the heads of the two lists. We traverse both lists simultaneously. When one pointer reaches the end of its list, it is redirected to the head of the other list. This ensures that both pointers traverse the same number of nodes before meeting at the intersection point. If there is no intersection, both pointers will eventually be NULL, and the loop will terminate. 

/**
 * 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) {
        
        ListNode *a = headA;
        ListNode *b = headB;

        while(a!=b){
            
            if(a==NULL)     a = headB;
            else            a = a->next;

            if(b==NULL)     b = headA;
            else            b = b->next;
        }
        return a;
    }
};

Code Complexity

Time Complexity: O(m + n)

The algorithm traverses both linked lists once, where 'm' and 'n' are the lengths of the two lists.

Space Complexity: O(1)

The algorithm uses only two pointers, ensuring constant space usage.

Code copied!