题目描述
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
样例
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。
算法1
第一种解法(暴力):
暴力遍历,时间复杂度为O(n^2),很有可能超时
用临时节点进行遍历,以防将链表B的表头走到末尾,第二次遍历时无法进入循环
注意每次遍历链表B之前,需要将临时节点赋值为表头
时间复杂度
O(n^2)
C++ 代码
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* pTemp=NULL;
for(;headA!=NULL;headA=headA->next)
{
pTemp=headB;
for(;pTemp!=NULL;pTemp=pTemp->next)
{
// 如果找到交点,则直接返回,否则继续遍历
if(headA==pTemp) return headA;
}
}
return NULL;
}
算法2
第二种解法(栈):
相交链表为Y字型,从尾向头遍历时,到交点处,会分叉
使用栈,将两个链表分别入栈,在出栈时进行遍历比较
直到遍历到某个不相同的节点时,该节点的前一个节点即是答案
时间复杂度
O(n),但会消耗栈的空间复杂度
C++ 代码
stack<ListNode*> sta1,sta2;
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
while(headA)
{
sta1.push(headA);
headA=headA->next;
}
while(headB)
{
sta2.push(headB);
headB=headB->next;
}
ListNode* pTemp=NULL;
// 需要先判断栈是否为空,如果栈为空,直接调用top()会造成内存错误
while(sta2.size()&&sta1.size()&&sta1.top()==sta2.top())
{
pTemp=sta1.top();
sta1.pop();
sta2.pop();
}
return pTemp;
}
算法3
第三种解法(差值):
计算两个链表的长度(分别为m、n),让较长的链表先走|m-n|步
然后两个链表同时同步速向后走,进行比较,如果遍历到的节点相同,则是交点
如果两个链表遍历完还没有交点,则返回NULL
时间复杂度
O(n)
C++ 代码
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 1、获取链表的长度,计算链表差值
int nLenA=0,nLenB=0,nSub=0;
ListNode* pTempA=headA;
ListNode* pTempB=headB;
while(pTempA)
{
++nLenA;
pTempA=pTempA->next;
}
while(pTempB)
{
++nLenB;
pTempB=pTempB->next;
}
// nSub=nLenA>nLenB?nLenA-nLenB:nLenB-nLenA;
// 2、让较长的链表先走差值步数
while(nLenA>nLenB)
{
--nLenA;
headA=headA->next;
}
while(nLenB>nLenA)
{
--nLenB;
headB=headB->next;
}
// 3、两个链表同时同步速向后遍历,同时比较是否相同
while(headA&&headB)
{
if(headA==headB) return headA;
else
{
headA=headA->next;
headB=headB->next;
}
}
// 如果有交点,在上述步骤3中肯定会返回某个节点,如果没有返回则表示两个链表遍历完也没有找到交点,即两个链表不相交
return NULL;
}