目录
一、判断单链表中是否有环
二、求有环单链表的环长
三、求有环单链表的环起点
四、求有环单链表的链表长度
五、代码实现
六、确定两个单向链表是否相交
核心：快慢指针（fast每次2步、slow每次1步）
参考 -1- - 2-
一、判断单链表中是否有环
使用两个指针从头开始扫描链表。
如果存在环，则两指针会相遇；如果不存在环指针fast遇到NULL退出；（追及相遇问题）
二、求有环单链表的环长
第二次相遇的时候，fast刚好比slow多走了1圈，即环长；
三、求有环单链表的环起点
pos：第一次碰撞点； LenA：起点到环起点的距离； x：环起点到第一次相遇点的距离
设环长为R；
第一次相遇：slow 走的长度 S=LenA+x；
fast 走的长度 2S=LenA+n*R+x；
则， LenA = n*R - x ；
即，让 fast 从 pos 出发，slow 从链表起点 head 出发，之后速度是相等的，那么相遇点即为环的起点
四、求有环单链表的链表长度
二中求得环长度，三中求得环起点位置，则可求出LenA，再加上环长即为链表长；
五、代码实现
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
struct node *nxt;
int val;
}node,*List;
/// 创建链表(链表长度，环节点起始位置)
List create()
{
List head=NULL;
node *preNode = head;
node *FifthNode = NULL;
for(int i=0;i<6;i++)
{
node *tt = new node();
tt->val = i;
tt->nxt = NULL;
if(preNode == NULL)
{
head = tt;
preNode = head;
}
else{
preNode->nxt =tt;
preNode = tt;
}
if(i == 3)
FifthNode = tt;
}
preNode->nxt = FifthNode;
return head;
}
///判断链表是否有环
node* judgeRing(List listt)
{
node *fast = listt;
node *slow = listt;
if(listt == NULL)return NULL;
while(true)
{
if(slow->nxt!=NULL && fast->nxt!=NULL && fast->nxt->nxt!=NULL)
{
slow = slow->nxt;
fast = fast->nxt->nxt;
}
else
return NULL;
if(fast == slow)return fast;
}
}
///获取链表环长
int getRingLength(node *ringMeetNode){
int RingLength=0;
node *fast = ringMeetNode;
node *slow = ringMeetNode;
for(;;)
{
fast = fast->nxt->nxt;
slow = slow->nxt;
RingLength++;
if(fast == slow)
break;
}
return RingLength;
}
///获取链表头到环连接点的长度
int getLenA(List listt, node *ringMeetNode)
{
int lenA=0;
node *fast = listt;
node *slow = ringMeetNode;
for(;;)
{
fast = fast->nxt;
slow = slow->nxt;
lenA++;
if(fast == slow)
break;
}
return lenA;
}
///环起始点
///如果有环, 释放空空间时需要注意.
node* RingStart(List listt, int lenA)
{
if (!listt || lenA<=0)return NULL;
int i = 0;
node* tmp = listt;
for ( ; i<lenA; ++i)
{
if (tmp != NULL)
tmp = tmp->nxt;
}
return (i == lenA)? tmp : NULL;
}
///释放空间
int freeMalloc(List listt, node* ringstart)
{
bool is_ringstart_free = false; //环起始点只能被释放空间一次
node *nextnode = NULL;
while(listt != NULL)
{
nextnode = listt->nxt;
if (listt == ringstart)
{ //如果是环起始点
if (is_ringstart_free)
break; //如果第二次遇到环起始点addr, 表示已经释放完成
else
is_ringstart_free = true; //记录已经释放一次
}
free(listt);
listt = nextnode;
}
return 0;
}
int main()
{
List listt = NULL;
node *ringMeetNode = NULL;
node *ringStartNode = NULL;
int LenA=0;
int RingLength = 0;
listt = create();
ringMeetNode = judgeRing(listt); //快慢指针相遇点
if(ringMeetNode == NULL)
printf("No Ring\n");
else{
printf("Have Ring\n");
RingLength = getRingLength(ringMeetNode); //环长
LenA = getLenA(listt,ringMeetNode);
printf("RingLength:%d\n", RingLength);
printf("LenA:%d\n", LenA);
printf("listLength=%d\n", RingLength+LenA);
}
ringStartNode = RingStart(listt, LenA); //获取环起始点
freeMalloc(listt, ringStartNode); //释放环节点, 有环时需要注意. 采纳5楼建议
return 0;
}
六、确定两个单向链表是否相交
首先，链表相交的概念：
如果两个单链表有共同的节点，那么从第一个共同节点开始，后面的节点都会重叠，直到链表结束。 因为两个链表中有一个共同节点，则这个节点里的指针域指向的下一个节点地址一样，所以下一个节点也会相交，依次类推。所以，若相交，则两个链表呈“Y”字形。
给定两个单链表的头结点head1、head2，判断这两个链表是否相交？
分为两种情况：有环 / 无环
判断链表是否有环
如果两个链表都没有环
plan1：先循环链表1，将每个节点的地址进行hash计算存入hash表，然后计算链表2的每个节点的地址的hash值，若与hash表中对应的位置有值则证明相交；plan2：令链表1和链表2首尾相连，判断新链表是否有环，有则相交；plan3：先计算两链表的长度L1，L2，若L1>L2，则现将链表1移动(L1-L2)个节点，等到两链表长度一样的时候一起向后移动，一次判断当前链表的结点是否相等，相等则相交；如果一个有环一个无环，则直接判断不相交如果两个都有环，则先分别得到两个链表的环的起点node1，node2
如果node1=node2，则相交；如果node1!=node2，则从一个链表的环的起点开始循环一周，判断是否有结点等于另一个链表的入环结点，若等，则相交
