/// 单链表判交问题,即是否有环,且环入口点,判断两个单链表是否相交
#include <stdio.h>
#include <malloc.h>
typedef struct Node
{
int data;
Node *next;
}Node;
/// @bried 判断是否有环
bool IsExitLoop(Node *head)
{
Node *slow = head;
Node *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
/// 两个指针从头开始走,一个走一步,一个走两步
/// 单链表存在环,就一定会相遇。
if(slow == fast)
{
break;
}
}
return !(NULL == fast || NULL == fast->next);
}
/// @brief 有环时,找到环的入口点。
Node *LoopEntryPoint(Node *head)
{
Node *slow = head;
Node *fast = head;
Node *first;
Node *crossPoint;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
/// 两个指针从头开始走,一个走一步,一个走两步
/// 单链表存在环,就一定会相遇。
/// 判断是否有环,且得出这两个指针在环中的相遇点
if(slow == fast)
{
break;
}
}
if(NULL == fast || NULL == fast->next)
{
return NULL;
}
first = head;
crossPoint = fast;
/*// 一个指针从头开始一步的移动,另一个从之前两个指针在环中的相遇点
/// 开始一步的移动,
/
当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n即至少一圈)。
假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,
因为在相遇点,相对于此点fast也至少走了一圈,即至少是第二次通过此点。
从此相遇点到链表的头与slow所走距离一样,即s
所以:2s = s + nr
即: s= nr
设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr //a+x这是slow走的路程,即s
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)
(L – a – x)为相遇点到环入口点的距离,
由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,
于是我们从链表头、与相遇点分别设一个指针,每次各走一步,
两个指针必定相遇,且相遇第一点为环入口点。
*/
while(first != crossPoint)
{
first = first->next;
crossPoint = crossPoint->next;
}
return first;
}
/// @brief 判断两个单链表是否相交,且得出相交点
/*如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,
我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以
走到同样的结尾点,则两个链表相交。这时我们记下两个链表length,再
遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链
表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点。
*/
Node *TwoListIntersecting(Node* head1,Node* head2)
{
int i;
int lenth1 = 0;
int lenth2 = 0;
int len = 0;
Node *L1 = head1;
Node *L2 = head2;
while(NULL != L1->next)
{
L1 = L1->next;
lenth1++;
}
while(NULL != L2->next)
{
L2 = L2->next;
lenth2++;
}
if(L1 != L2)
{
fprintf(stdout,"they are not intersecting\n");
return NULL;
}
L1 = head1;
L2 = head2;
if(lenth1 >= lenth2)
{
len = lenth1 - lenth2;
for(i=0; i<len; i++)
{
L1 = L1->next;
}
}
else if(lenth1 < lenth2)
{
len = lenth2 - lenth1;
for(i=0; i<len; i++)
{
L2 = L2->next;
}
}
while(L1 == L2)
{
L1 = L1->next;
L2 = L2->next;
}
return L1;
}
Node *CreateLoopList()
{
int i;
Node *tmp,*current,*pLoop;
Node *head = (Node *)malloc(sizeof(Node));
head->data = 0;
head->next = NULL;
tmp = head;
for(i=0; i<10; i++)
{
current = (Node *)malloc(sizeof(Node));
current->data = i;
if(5 == i)
{
pLoop = current;
}
current->next = tmp->next;
tmp->next = current;
tmp = current;
current = NULL;
}
#if 0
/// @brief 设置环节点
current = (Node *)malloc(sizeof(Node));
current->data = i;
current->next = pLoop;
tmp->next = current;
tmp = current;
current = NULL;
#endif
return head;
}
void printfList(Node* head)
{
Node *tmp = head;
while(tmp->next)
{
printf("data[%d]\n",tmp->next->data);
tmp = tmp->next;
}
}
int main(int argc,char *argv[])
{
int flag;
Node *tmp = NULL;
Node *head = NULL;
Node *tt = NULL;
Node *xx = NULL;
head = CreateLoopList();
printfList(head);
flag = IsExitLoop(head);
if(flag == true)
{
printf("have loop\n");
}
else
{
printf("have no loop\n");
}
xx = LoopEntryPoint(head);
//printf("the loop entry point data[%d]\n",tmp->data);
tmp = CreateLoopList();
printfList(tmp);
tt = TwoListIntersecting(tmp, head);
if(NULL == tt)
{
fprintf(stdout,"have no crossing\n");
}
else
{
fprintf(stdout,"yes a crossing data[%d]\n",tt->data);
}
return 0;
}