# 160. 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.

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

C++ 解法一：

``````class Solution {
public:
if (lenA < lenB) {
for (int i = 0; i < lenB - lenA; ++i) headB = headB->next;
} else {
for (int i = 0; i < lenA - lenB; ++i) headA = headA->next;
}
}
}
int cnt = 0;
++cnt;
}
return cnt;
}
};
``````

Java 解法一：

``````public class Solution {
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; ++i) headA = headA.next;
} else {
for (int i = 0; i < lenB - lenA; ++i) headB = headB.next;
}
}
}
int cnt = 0;
++cnt;
}
return cnt;
}
}
``````

C++ 解法二：

``````class Solution {
public:
while (a != b) {
a = a ? a->next : headB;
b = b ? b->next : headA;
}
return a;
}
};
``````

Java 解法二：

``````public class Solution {
while (a != b) {
a = (a != null) ? a.next : headB;
b = (b != null) ? b.next : headA;
}
return a;
}
}
``````

Minimum Index Sum of Two Lists