两个单链表相交的一系列问题
2020-04-08 本文已影响0人
李海游
在本题中，单链表可能有环，也可能无环。给定两个 单链表的头节点 head1和head2，这两个链表可能相交，也可能 不相交。请实现一个函数， 如果两个链表相交，请返回相交的 第一个节点；如果不相交，返回null 即可。
要求：如果链表1 的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外 空间复杂度请达到O(1)。
题目来自 左程云 《程序员代码面试指南》
分析：
从链表有没有环来说，可以分为三种情况：
1）两个链表均为单链表，无环；
2）两个链表，1个有环，一个无环；
3）两个链表全有环。
下面从这三种情况分别分析。
1）两个链表均为单链表，无环
如果两个链表长度相同，那么如果两个链表的某个结点相等，那么返回该结点即可。如果不等，同时next。
但是两个链表长度可能会不一样。这时可以先获取两个链表的长度，让长链表先走长度差那么多步，这时两个链表长度也就相等了。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int numA=0,numB=0;
ListNode *pa=headA,*pb=headB;
while(pa!=NULL&&pb!=NULL) //两个同时走，直到一个为空
{
pa=pa->next;
pb=pb->next;
++numA;
++numB;
}
while(pa!=NULL) //这个和下面的while，两个只能发生一个
{
pa=pa->next;
++numA;
}
while(pb!=NULL)
{
pb=pb->next;
++numB;
}
pa=headA;
pb=headB;
if(numA>numB) //A长
{
while(numA-numB) //A先走
{
pa=pa->next;
--numA;
}
}
else //B长
{
while(numB-numA) //B先走
{
pb=pb->next;
--numB;
}
}
while(pa!=NULL&&pb!=NULL) //两个同时走
{
if(pa==pb)
return pa;
else
{
pa=pa->next;
pb=pb->next;
}
}
return NULL;
}
};
2）两个链表，1个有环，一个无环
这种情况是不可能相交的，...
3）两个链表全有环。
- 全有环但是不相交
这种情况就是两个链表各自成环，那么可以链表A结点处在环的入口处，另链表B从环入口结点处一直走环，如果转了一圈，还没有遇到A的结点，那么就说明两个链表不相交。 - 全有环，相交意味着环是一样的，一种情况是在进入环之前两个链表已经相交。
那么这个时候第一个相交的结点不在环里面。此时，可以想象将两个链表从头部截断到各自的环的入口处，那么就化解成，两个单链表找第一个相交的结点了。 - 全有环，相交意味着环是一样的，另一种情况是在两个链表进入环的入口不同。
此时返回任一个应该都正确。可以同样通过A不动，B转一圈，遇到A就说明相交了。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast=head;
ListNode *slow=head;
bool hasCycle=false;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
hasCycle=true;
break;
}
}
slow=head;
while(hasCycle)
{
if(slow!=fast)
{
slow=slow->next;
fast=fast->next;
}
else
return slow;
}
return NULL;
}
};
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode * firAcycle=detectCycle(headA);
ListNode * firBcycle=detectCycle(headB);
if(firAcycle==firBcycle) //说明两个环入口一样，第二种情况
{
//转换成 第一种无环相交 不过这次 尾结点不是 NULL，而是 firAcycle 和 firBcycle
}
else // 可能不相交 也可能两个环的入口不一样
{
ListNode *tmp=firAcycle->next;
while(tmp!=firAcycle)
{
if(tmp==firBcycle) //第三种情况 相交 环入口不一样
return firBcycle;
tmp=tmp->next;
}
return false; //不相交
}
}
// 有环的话返回入口结点，无环返回NULL
ListNode *detectCycle(ListNode *head) {
ListNode *fast=head; //快慢双指针
ListNode *slow=head;
bool hasCycle=false;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast) //相等有环 记录相遇结点
{
hasCycle=true;
break;
}
}
slow=head;
while(hasCycle)
{
if(slow!=fast)
{
slow=slow->next;
fast=fast->next;
}
else
return slow;
}
return NULL;
}
};
