# Intersection of Two Linked Lists Problem & Solution

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

## C++ Solution

The runtime complexity of the algorithm is $O(n + m)$.

#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
* struct ListNode {
*   int val;
*   ListNode *next;
*   ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = 0;
ListNode* cursorA = headA;
while (cursorA != nullptr) {
cursorA = cursorA->next;
++lenA;
}

int lenB = 0;
ListNode* cursorB = headB;
while (cursorB != nullptr) {
cursorB = cursorB->next;
++lenB;
}

while (lenA > lenB) {
headA = headA->next;
--lenA;
}

while (lenB > lenA) {
headB = headB->next;
--lenB;
}

// At this step, lenA == lenB.
while (lenA > 0) {
if (headA == headB) {
return headA;
}

headA = headA->next;
headB = headB->next;
--lenA;
}

return nullptr;
}
};


## Sample Search Queries

Many Paths. Follow Yours.