给出两个单链表的头结点headA与headB，让我们找出两个链表相接的起始节点，如果两个链表不存在相交结点返回null。
我们就先假设存在这样两个链表，链表1与链表2，假设链表1的长度为 L 1 L_1 L1和 L 2 L_2 L2,假设对于两个链表，从相交的结点向后数长度为 L 1 , 2 L_{1,2} L1,2,则在相交结点之前链表1的长度未 L 1 − L 1 , 2 L_1-L_{1, 2} L1−L1,2链表2的长度为 L 2 − L 1 , 2 L_2- L_{1, 2} L2−L1,2,对于两条链表无相交的情况 L 1 , 2 = 0 L_{1,2}=0 L1,2=0,如图是具有相交部分的两个链表的图示：
不相交的两个链表的图示你可以想象出来，将后面的那一部分去掉就行了。
我们现在想的就是如何让遍历链表1的指针与遍历链表2的指针能够相遇在同一节点，如图所示：
显然这两个链表在相交部分前面的部分可能不一样长也就是 L 1 ≠ L 2 L_1\neq L_2 L1=L2,也就是我们我们直接从头结点遍历遍历到尾结点是不行的，我们们来看一下遍历到尾节点之后链表1走了多远 ( L 1 − L 1 , 2 ) + L 1 , 2 (L_1-L_{1,2})+L_{1,2} (L1−L1,2)+L1,2链表2走过的长度为 ( L 2 − L 1 , 2 ) + L 1 , 2 (L_2-L_{1,2})+L_{1,2} (L2−L1,2)+L1,2是不是我们可以看出有一段是公共的长度，它们两个走过的长度不一样就不一样在 ( L 1 − L 1 , 2 ) (L_1-L_{1,2}) (L1−L1,2)与 ( L 2 − L 1 , 2 ) (L_2-L_{1,2}) (L2−L1,2)这两项上，如果说在链表1走过的路程加上一个 ( L 2 − L 1 , 2 ) (L_2-L_{1,2}) (L2−L1,2),在链表2走过的路程加上一个 ( L 1 − L 1 , 2 ) (L_1-L_{1,2}) (L1−L1,2)，它们是不是就一样了，都为 ( L 1 − L 1 , 2 ) + L 1 , 2 + ( L 2 − L 1 , 2 ) (L_1-L_{1,2})+L_{1,2}+(L_2-L_{1,2}) (L1−L1,2)+L1,2+(L2−L1,2)
我们整理一下：
链表1走过的路程为： { ( L 1 − L 1 , 2 ) + L 1 , 2 } + ( L 2 − L 1 , 2 ) \{(L_1-L_{1,2})+L_{1,2}\}+(L_2-L_{1,2}) {(L1−L1,2)+L1,2}+(L2−L1,2)
链表2走过的路程为： ( L 1 − L 1 , 2 ) + { ( L 1 , 2 ) + ( L 2 − L 1 , 2 ) } (L_1-L_{1,2})+\{(L_{1,2})+(L_2-L_{1,2})\} (L1−L1,2)+{(L1,2)+(L2−L1,2)}
在这两个式子中，我们发现{}所围的为自己链表的长度，其余的为对方链表的在相交之前的部分的长度。也就是说如果我们遍历自身链表，到结尾之后再去遍历对方链表就能让两个指针同步。
两个指针同步之后，如果在同步之后后面仍有结点，则说明有相交部分，如果同步之后后面没有结点了，则说明这两个链表之间没有相交部分。
有了上面的思路，我们可以写出下面的代码：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *p=headA, *q=headB;
while(p!=q){
if(p==NULL){
p = headB;
}else{
p = p->next;
}
if(q==NULL){
q = headA;
}else{
q = q->next;
}
}
return p;
}
而且程序的时间复杂度为 O ( n + m ) O(n+m) O(n+m)空间复杂度为 O ( 1 ) O(1) O(1)
程序运行结果：