单链表往期文章：
单链表(算法面试题2)---单链表进阶2 一题多解，逐步优化
问题描述：
给定两个可能有环也有可能无环的单链表,头节点head1和head2
请实现一个函数如果两个链表相交,请返回相交的第一个节点
如果不相交,返回NULL。
解题思路：
1.判断两链表有没有环
通过快慢指针进行判断，如果有环，则两个指针一定会相遇，否则无环。
2.什么样的两个单链表才会相交
两个链表的组合可能性：
1).两个链表均无环---->有可能相交
2).两个链表均有环---->也可能相交
3).一个有环一个无环--->不可相交(如果相交则一定共用一个环或者共用最后一个节点)
3.无环链表相交问题
1)判断两个无环链表是否相交。只需要考虑他们是否共用了最后一个节点即可，
如果共用则相交，否则一定不相交。
2)找到相交的节点，并返回
==》通过两个链表的长度来找。如果链表A与链表B相交，len(A)>len(B)
那么我们可以知道A比B长len(A)-len(B),不妨让指向A的指针先走len(A)-len(B)的 长度，再让指向A和指向B的指针同时走，当pA==pB时，到达交点。
4.有环链表相交问题
1)判断两个有环链表是否相交。
如果相交，则有两种情况：
情况1:在环外相交(包括在入环节点处相交)--->那么他们一定共用一个入环节点。
情况2:在环内相交--->可以让一个指针追另外一个指针，如果能相遇则相交
否则，不相交，返回NULL
代码如下：
//通过快慢指针,如果有环,则最后一定会相遇 //有环-->则返回第一个入环节点 //无环-->返回NULL Node getLoopNode(Node head){ //如果为空链表或着只有一个节点或者两个节点则不可能有环 if(head == NULL || head->next == NULL || head->next->next == NULL){ return NULL; } //slow fast Node slow = head->next; Node fast = head->next->next; while(slow != head){ if(head->next == NULL || head->next->next == NULL){ return NULL; } slow = slow->next; fast = fast->next->next; } //找到入环节点-->把快指针指向头部，重新开始， //当慢指针与快指针再次相遇时，相遇点一定是入环的第一个节点 fast = head; while(fast != slow){ fast = fast->next->next; slow = slow->next; } return slow; } //如果两个链表的无环，返回第一个相交点，如果不相交，返回NULL Node noLoop(Node head1,Node head2){ if(head1 == NULL || head2 == NULL){ return NULL; } //如果相交,则最后一定共用最后一个节点 int n = 0; Node cur1 = head1; Node cur2 = head2; while(cur1->next != NULL){ n++; cur1 = cur1->next; } while(cur2->next != NULL){ n--; cur2 = cur2->next; } if(cur1 != cur2)//如果没有共用一个最后一个节点,则一定不相交 { return NULL; } cur1 = n > 0 ? head1:head2; cur2 = cur1==head1 ? head2:head1; n = abs(n); while(n != 0){ n--; cur1 = cur1->next; } while(cur1 != cur2){ cur1 = cur1->next; cur2 = cur2->next; } return cur1; } //两个有环链表 /* * 1.不相交 2.在环外相交(一定共用一个入环节点) 2.在环内相交 */ Node bothLoop(Node head1,Node loop1,Node head2,Node loop2){ Node cur1 = NULL; Node cur2 = NULL; if(loop1 == loop2){ //在环外相交或者在入环处相交 int n = 0; cur1 = head1; cur2 = head2; while(cur1 != loop2){ n++; cur1 = cur1->next; } while (cur2 != loop2) { n--; cur2 = cur2->next; } if(cur1 != cur2){ return NULL; } cur1 = n>0 ? head1:head2; cur2 = cur1==head1 ? head2:head1; while(n != 0){ n--; cur1 = cur1->next; } while(cur1 != cur2){ cur1 = cur1->next; cur2 = cur2->next; } return cur1; }else{ //如果是相交在环内,让一个指针区追另一个 cur1 = loop1; while(cur1 != loop1){ if(cur1 == loop2){ return cur1; } cur1 = cur1->next; } return NULL; } } Node getIntersectNode(Node head1,Node head2){ if(head1 == NULL || head2 == NULL){ return NULL; } Node loop1 = getLoopNode(head1); Node loop2 = getLoopNode(head2); //两个链表如果相交的话,一定是两个都无环或者两个都有环 /*因为有环相交的环，他们一定有一个共用的环*/ if(loop1 == NULL && loop2 == NULL){ //无环 return noLoop(head1,head2); } if(loop1 != NULL && loop2 != NULL){ //有环 } return NULL; }
