坂田做网站的公司西安百度推广优化托管

题目描述

给你两个单链表的头节点 headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构 。

解题思路

暴力求解

在A链表中遍历每一个结点，去B链表中依次找一遍，但是这种方法的时间复杂度为O(N^2)，因此，这种方法想必不太好，就不写代码实现了。

优雅解法

我们可能会这样想，如果在交点前同样距离远的位置同时开始遍历两个链表，那么在接下来的遍历过程中肯定会遍历到同一个结点，当第一次遍历到同一个结点时，那么这个结点就必然是交点。那么问题来了，我们刚才的假设是在交点前同样距离远的位置同时开始遍历两个链表，那么怎么才能做到这样呢？这两个链表的长度很可能是不一样的。我们这样想，分别遍历A、B这两个链表，同时计算这两个链表的长度，如果最终遍历到同一个结点，那么这两个链表必然相交，因此我们也可以计算出这两个链表长度的差值（假设为dif）。得到的这个差值很关键，我们让较长的链表先开始走dif步，然后两个链表再同时继续遍历，当遍历到同一个结点时，这个结点就是交点。

实现代码如下：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode* curA=headA;struct ListNode* curB=headB;int sizeA=1;int sizeB=1;while(curA->next){curA=curA->next;sizeA++;}while(curB->next){curB=curB->next;sizeB++;}//判断相交if(curA != curB)return NULL;int dif=abs(sizeA-sizeB);curA=headA;curB=headB;//长的先走dif步if(sizeA > sizeB){while(dif--){curA=curA->next;}}else{while(dif--){curB=curB->next;}}//一起走while(curA != curB){curA=curA->next;curB=curB->next;}return curA;  
}