文章目录
- 1. 题目介绍
- 2. 思路1:暴力求解
- 算法思想
- 代码实现
- 3. 思路2:快慢指针
- 算法思想
- 代码实现
1. 题目介绍
链接: link
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
2. 思路1:暴力求解
算法思想
首先第一种思路就是暴力求解,这可能是我们最容易想到的:
让A链表的每个结点依次与B中所有结点逐个比较(拿B的跟A比也是一样),当然这里要注意比较的时候应该比较结点的地址,而不应该比较结点的值。结点的值一样并不能证明它们相交。
这种方法思想很简单,但是效率不好,这样的话时间复杂度就是O(N^2)
代码实现
代码也很简单,可以给大家写一下:
也可以通过。
//暴力求解,让A链表的每个结点依次与B中所有结点逐个比较。O(N^2)
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
struct ListNode* curA = headA;
struct ListNode* curB = headB;
while (curA)
{
curB=headB;
while (curB)
{
if (curA == curB)
return curA;
curB = curB->next;
}
curA = curA->next;
}
return NULL;
}
但是上面的算法效率不是很好,我们能不能优化一下呢?
3. 思路2:快慢指针
算法思想
大家思考一个问题:
上面我们暴力比对结点的地址来寻找链表的交点。
但是为什么要拿A链表的每个结点依次与B中所有结点逐个比较呢?
为什么不能同步的遍历两个链表,比较对应的结点呢?
如果同步遍历话,就是O(N)
了
🆗,不能直接这样,因为两个链表的长度可能是不一样的。
比如像这样
如果我们同步的遍历去比对,显然是不行的,不能得到正确的结果。
那不能直接同步遍历两个链表的去比较,我们能不能想个办法让他们可以同步遍历去比较呢?
我们来分析一下。
如果两个链表相交,但是长度不相等,那么不相等的部分一定是在交点之前的。
因为相交之后它们后面的结点都是一样的嘛。
那上面我们分析了,就是因为两个链表的长度可能不一样,所以不能同步遍历去比较。
那我们能不能把他们变成一样长呢?
🆗,我们可以这样做
我们可以同步遍历去比较。
但是,如果长度不相等,我们要先让较长的那个链表的遍历指针先走长度的差值步
此时,我们看到,是不是就可以让curA和curB同时往后走,比较对应的结点了。
这样如果它们有交点的话,就一定会出现curA==curB,此时这两个指针指向的结点就是第一个交点,返回curA或curB都可。
如果没有交点,那就一直往后走curA不会和curB相等,遍历结束,curA和curB都走到空,返回curA或curB都可。(当然待会大家看我们的代码,不相交的话我们在求长度差值的时候其实就能判断出来了)
所以:
我们可以先遍历一遍两个链表,求出它们的长度,判断出谁长谁短,并计算出长度的差值。
然后让长的链表先走差值步,再同步往后走,比较对应结点,找交点。
代码实现
理清了思路,我们来写一下代码:
提交一下:
过啦!
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *curA=headA;
struct ListNode *curB=headB;
int lenA=0;
int lenB=0;
//找尾,先判断是否相交,不相交直接返回NULL,相交再找
while(curA->next)
{
lenA++;
curA=curA->next;
}
//计算准确长度应该这样写:while(curA)
//这样while(curA->next)比实际长度小1,但是两个都小1,不影响差值
//而这样写循环结束cur就是尾,可直接判断是否相交
while(curB->next)
{
lenB++;
curB=curB->next;
}
//尾不相等,则不相交
if(curA!=curB)
return NULL;
//计算差值
int gap=abs(lenA-lenB);
//找出长的那一个
struct ListNode *longlist=headA;
struct ListNode *shortlist=headB;
if(lenB>lenA)
{
longlist=headB;
shortlist=headA;
}
//长表先走差值步
while(gap--)
{
longlist=longlist->next;
}
//再一起走,比较两个链表的当前结点是否相同
//,第一个相同的就是第一个交点
while(longlist!=shortlist)
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return longlist;
}