相交链表（给你两个链表，找出它们的第一个公共结点）的实现与讲解

一：题目

二：思路讲解

1：应该是先判断是否相交。

2：相交就计算出相交前的两条链表的长度差距

3：让长的那一条链表先走长度的差距，这样会距离交点的距离相等，然后再对两条链表的节点对应着去比较。

第一步：判断是否相交

两个链表如果相交，他们的尾节点一定相同，因为，一但有一个相交节点，比如图中的c1，那之后的链表一定是一致的，因为一个节点只能指向一个节点，所以尾节点相同则两个链表一定相交！ 

第二步：计算长度差距，并让长的链表往后走差距长度就一样长了

因为：长度的差距一定是在相交节点之前就决定了的，因为相交节点之后的链表完全相同。

 代码展示：

注意：

1：lenA为什么为1，因为while（curA->next）只能让cur停留在尾节点上，所以尾节点并没有经过，lenA也少一个+1，lenB同理。

那为什么不while（curA） 呢，这样lenA就是正确的，因为下面的尾节点比较的时候，curA和curB已经来到了尾节点的后一个节点，这样的话无法比较尾节点，除非在计算长度的时候，还要保留前一个节点的指针，这样比较麻烦，所以宁愿lenA，lenB赋值为1.

2：abs函数为计算两个值的差值的绝对值

3：longlist  就是我们希望的长的链表， shortlist就是我们希望的短的链表

4：最后出循环的时候，代表两个节点相同了，这时候返回longlist和shortlist都可以

原文地址：https://blog.csdn.net/shylyly_/article/details/138669787

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！