Leetcode. 160相交链表

指针解法

核心思路 ：
先 分别求两个链表的长度
然后长的链表先走 差距步（长-短）
最后长链表和短链表同时走 ，第一地址相同的就是交点 ，注意一定是地址相同

不可能出现上图这种情况 ，因为C1这个节点只有一个next ，不会有两个next

---

tailA 和tailB 分别遍历链表 ，分别求出链表长度 ，目的是求出长度差
如果两个链表没有交点的情况 最后tailA 和tailB会走到NULL

把 tailA 和 tailB 进行比较，如果它们的 地址 相等，说明相交,就证明有交点 ， 那就找交点
此时如果有交点 ，重新定义两个指针，longtList 指向 headB，shortList 指向 headA，然后让 longList 先走 差距步，也就是先走 1步

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{int lenA = 1 ;int lenB =1 ;struct ListNode * tailA = headA  , *tailB =headB ;//分别求两个链表的长度while (tailA->next){tailA= tailA->next ;lenA ++ ;}while (tailB->next){tailB= tailB->next ;lenB++ ;}int gap = abs (lenA -lenB);//计算差距步struct ListNode * longList = headA  ,*shortList=headB ;  // 假设headA 是长链表if( lenA<lenB)     //如果headA不是长链表 ,强行变成长链表{longList =headB ;shortList=headA ;}while(gap--)  //长的链表先走差距步{longList=longList->next ;   }//寻找节点 地址相同就是节点while( longList != shortList ){longList=longList->next ;shortList=shortList->next ;}return longList ;}

这种方法可以做到时间复杂度O(N) 空间复杂度 为O(1)

如果你觉得这篇文章对你有帮助，不妨动动手指给点赞收藏加转发，给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力！！！