Programming Skills: Intersection of Two Linked Lists

[Problem]
https://leetcode.com/problems/intersection-of-two-linked-lists/

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

For example, the following two linked lists:

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

begin to intersect at node c1.

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.

[Solution]

2 pointer traverse 2 list wisely,
then they will travel the same distance, and meet at the same point.

Use pointer p1=headA, p2=headB to traverse the list step by step simutaniously.
While(p1!=NULL && p2!=NULL)
If p1==p2,
return p1 (you got the intersection point).
else
p1 & p2 moving forward
if (both of them reach the NULL)
return NULL (no intersection)
if(p1 reach NULL)
move p1 to headB.
if(p2 reach NULL)
move p2 to headA.

The reason we design RED part is :
ListA is composed by 'unique part'(with len A) + 'intersection part'(with len I).
ListB is composed by 'unique part'(with len B) + 'intersection part'(with len I).

The distance p1 walk through is A+I+B.

The distance p2 walk through is B+I+A.

Now you can see that p1 and p2 will walk through the same distance,

and meet at the head of intersection part.


class Solution {
public:
    
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p1=headA, *p2=headB;
        while(p1 && p2){
            if(p1==p2) return p1;
            p1=p1->next;
            p2=p2->next;
            if(p1==p2) return p1;
            if(!p1) p1=headB;
            if(!p2) p2=headA;
        }
        return NULL;
    }
};