class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
ListNode *pA = headA, *pB = headB;
int lenA = 0, lenB = 0;
while(pA) pA = pA>next, lenA++;
while(pB) pB= pB>next, lenB++;
pA = headA, pB = headB;
if(lenA > lenB) for(int i = 0; i < lenAlenB; ++i) pA = pA>next;
else for(int i = 0; i < lenBlenA; ++i) pB = pB>next;
while(pA)
{
if(pA == pB) return pA;
pA = pA>next;
pB = pB>next;
}
return NULL;
}
};
Simple yet best solution in C++


Actually we can also use
set
here which is quite intuitive, though performance is not good.class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<ListNode*> node_set; ListNode *p = headA; while(p) { node_set.insert(p); p = p>next; } p = headB; while(p) { if(!node_set.insert(p).second) return p; p = p>next; } return NULL; } };