题目如下(题目来源力扣):
个人解题思路:
运用双指针,第一次遍历先一起走,当一个走到尾时开始计数,等另一个指针也走到尾时记录下两个指针的路程差,同时比对两个指针指向的地址是否相同,以此判断两个链表是否相交。
如果相交,则让两个指针回到两个单链表开头,让链表长的那个先走完两指针的路程差,然后再将两个指针同时启动,每走一步都比对两个指针指向地址,当两指针指向地址相同时,就是两个单链表相交的第一个相交节点。
代码实操:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int distance = 0;
int flag = 0;//相交标志
struct ListNode* fast = headA;
struct ListNode* slow = headB;
//确定是否存在交点
while(fast->next && slow->next)
{
fast = fast->next;
slow = slow->next;
}
if(fast->next == NULL)//fast指针先走完
{
while(slow->next)
{
slow = slow->next;
distance++;//当一个指针走到最后一个节点时,确定两个指针的距离
}
if(fast == slow)
flag = 1;
fast = headA;
slow = headB;
}
else//slow指针先走完
{
while(fast->next)
{
fast = fast->next;
distance++;//当一个指针走到最后一个节点时,确定两个指针的距离
}
if(fast == slow)
flag = 1;
fast = headB;
slow = headA;
}
if(flag)//存在交点
{
//令走的慢的指针先走“距离”步数,然后再两个指针同时走,检测是否相交
while(distance--)
{
slow = slow->next;
}
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
}
else
{
return NULL;
}
printf("Intersected at '%d'",fast->val);
return fast;
}