【数据结构与算法】相交链表求交点
【摘要】 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
方法一:双循环对比法(暴力解法效率较低，不建议采用)
方法二: 双指针法
一、问题描述
如下图所示
二、解题思路
方法一:双循环对比法
- 时间复杂度O（n^2） 空间复杂度O（1）
- 链表A中的节点依次与链表B中的每个节点比较
- 若出现节点相同，则相交且为第一个交点
- 若链表A走到空依然没有相同的节点，则不相交
注意：暴力解法效率较低，不建议采用
方法二: 双指针法
- 时间复杂度O（n) 空间复杂度O（1）
- 首先遍历链表求出两个链表的长度，求得长度的差值
- 定义两个快慢指针，哪个链表长，快指针就指向哪个链表
- 两个指针分别从两个链表的第一个节点开始遍历，快指针先走出一个长度差值，之后两个指针每移动一步，比较指向的节点是否相同
- 若出现节点相同，则相交且为第一个交点
- 若两个指针走到空依然没有相同的节点，则不相交
三、C语言代码实现
方法一实现代码
struct ListNode
{
int val;
struct ListNode *next;
};
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
ListNode*pcurA=headA;
ListNode*pcurB=headB;
while(pcurA)
{
pcurB=headB;
while(pcurB)
{
if(pcurA==pcurB)
return pcurA;
pcurB=pcurB->next;
}
pcurA=pcurA->next;
}
return NULL;
}方法二实现代码
struct ListNode
{
int val;
struct ListNode *next;
};
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
ListNode*pcurA=headA;
ListNode*pcurB=headB;
int countA=0;
int countB=0;
while(pcurA)//求出链表长度
{
pcurA=pcurA->next;
countA++;
}
while(pcurB)
{
pcurB=pcurB->next;
countB++;
}
int tmp=abs(countA-countB);//长度差值
ListNode*slow,*fast;
if(countA<countB)
{
slow=headA;
fast=headB;
}
else
{
slow=headB;
fast=headA;
}
while(tmp--)//长链表先走差值的步数
{
fast=fast->next;
}
while(fast&&slow)//同步比较
{
if(fast==slow)
return fast;
fast=fast->next;
slow=slow->next;
}
return NULL;
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）