前言
本系列主要讲解链表的经典题 注:划重点!!必考~
链表分割
给你两个单链表的头节点
headA
和headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回null
。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//创建寻址指针
struct ListNode*cur1=headA,*cur2=headB;
//计算各链表的长度
int len1=1,len2=1,gas;
while(cur1->next)
{
len1++;
cur1=cur1->next;
}
while(cur2->next)
{
len2++;
cur2=cur2->next;
}
//各链表尾节点不相等则两链表不相交
if(cur1!=cur2)
return false;
//接下来则是必定有相交节点的情况
//判断长短并记录
struct ListNode*geater,*less;
if(len1>=len2)
{
geater=headA;
less=headB;
gas=len1-len2;
}
else
{
geater=headB;
less=headA;
gas=len2-len1;
}
//长链表先走差距长度
while(gas--)
{
geater=geater->next;
}
//一同走,相等时则找到相交节点
while(geater!=less)
{
geater=geater->next;
less=less->next;
}
return geater;
}
每日k题无烦恼,点赞学习不得了~