image.png
http://bangbingsyb.blogspot.com/2014/11/leetcode-intersection-of-two-linked.html
找链表交界，很类似Linked List Cycle II那题，方法也是类似的双指针相遇法。分两步走：
- 如何判断两链表是否相交？
两链表相交则他们必然有共同的尾节点。所以遍历两两链表，找到各自的尾节点，如果tailA!=tailB则一定不相交，反之则相交。
- 如何判断两链表相交的起始节点？
在第1步判断相交时可以顺带计算两链表的长度lenA和lenB。让长的链表的head先走abs(lenA-lenB)步，然后和短链表的head一起走，直到两者相遇，即为要找的节点。
解法一 （两根指针）：
先遍历一遍，看a和b的长度，然后长的那个先走l2 - l1 步，然后一起走。
/**
* 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) {
int l1 = 0, l2 = 0;
ListNode * p1 = headA;
ListNode * p2 = headB;
while(p1){
p1 = p1->next;
l1++;
}
while(p2){
p2 = p2->next;
l2++;
}
p1 = headA;
p2 = headB;
if(l1 > l2){
for(int i = 0; i < l1 - l2; i++){
p1 = p1->next;
}
}
else{
for(int i = 0; i < l2 - l1; i++){
p2 = p2->next;
}
}
while(p1 && p2){
if(p1 == p2){
return p1;
}
else{
p1 = p1->next;
p2 = p2->next;
}
}
return NULL;
}
};
解法二：
https://zhuanlan.zhihu.com/p/32997648
You can prove that: say A length = a + c, B length = b + c, after switching pointer, pointer A will move another b + c steps, pointer B will move a + c more steps, since a + c + b + c = b + c + a + c, it does not matter what value c is. Pointer A and B must meet after a + c + b (b + c + a) steps. If c == 0, they meet at NULL.
当p1走完时，接着head2,当p2走完是，接着head1,设l1长度（a+c）
l2长度（b+c）,所以换完pointer之后，因为(a+c+b+c) = (b+c+a+c)；
所以如果不管有没有交叉，最后都在C;如果没有交叉,为NULL;
如果有交叉，那么在前退C步的时候，相遇，即（a+c+b） = (b+c+a)
/**
* 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) {
if(headA == NULL || headB == NULL){
return NULL;
}
ListNode *p1 = headA;
ListNode *p2 = headB;
while(p1 != p2){
p1 = p1 == NULL ? headB : p1->next;
p2 = p2 == NULL ? headA : p2->next;
}
return p1;
}
};
解法三：哈希
用哈希表也可以过！！！！！找到了新大陆！！！！
/**
* 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) {
map<ListNode *, int> hash_map;
ListNode * p1 = headA, *p2 = headB;
while(p1){
hash_map[p1] = 1;
p1 = p1->next;
}
while(p2){
if(hash_map[p2] == 1){
return p2;
}
p2 = p2->next;
}
return NULL;
}
};
