当前位置：首页 > news >正文

Leetcode. 160相交链表

news 2025/8/26 4:04:44

文章目录

指针解法

指针解法

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

在这里插入图片描述

不可能出现上图这种情况，因为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 ;}