程序员面试笔试宝典 判断链表是否有环
发布网友
发布时间：2022-04-26 14:56
共1个回答
热心网友
时间：2023-04-28 13:42
设置两指针slowfast,初始值均指向链表,slow每向前走步,fast每向前走两步.
链表环,则fast先进入环,slow进入环,两指针环必定相遇.
slow与fast没相遇,fast遍历链表尾部,则表示链表没环.
2.链表环,确定环入口点
设置slow指针指向链表,fast指向相遇点,每两指针都走步,两指针必定相遇,
则相遇第点环入口点.
3.计算环
环入口点设置指针计数器,让指针环面走,每走步,计数器加1,
指针环入口点候,计数器值环.
测试结:
链表1:
10 20 30 40 50 20 30 40 50 20 30 40 50 20 30 40 50 20 30 40
环入口点: 20
环: 4
链表2:
1 2 3 4 5
链表没环
//C语言测试程序
#include
#include
typedef struct Node
{
int data;
struct Node *next;
}Node,*LinkList;
//创建链表("环")
LinkList CreateLinkWithLoop()
{
LinkList head; //链表
Node *newNode; //新结点
Node *ptr; //指向前结点
Node *pEntry; //指向"环"入口
newNode=(Node *)malloc(sizeof(Node));
newNode->data=10;
newNode->next=NULL;
head=newNode; //设置链表
ptr=newNode;
newNode=(Node *)malloc(sizeof(Node));
newNode->data=20;
newNode->next=NULL;
ptr->next=newNode;
ptr=newNode;
pEntry=newNode; //指向"环"入口
newNode=(Node *)malloc(sizeof(Node));
newNode->data=30;
newNode->next=NULL;
ptr->next=newNode;
ptr=newNode;
newNode=(Node *)malloc(sizeof(Node));
newNode->data=40;
newNode->next=NULL;
ptr->next=newNode;
ptr=newNode;
newNode=(Node *)malloc(sizeof(Node));
newNode->data=50;
newNode->next=pEntry; //产"环"
ptr->next=newNode;
ptr=newNode;
return head;
}
//创建链表(没"环")
LinkList CreateLink()
{
LinkList head; //链表
Node *newNode; //新结点
Node *ptr; //指向前结点
int i;
newNode=(Node *)malloc(sizeof(Node));
newNode->data=1;
newNode->next=NULL;
head=newNode; //设置链表
ptr=newNode;
for(i=2;i<=5;i++)
{
newNode=(Node *)malloc(sizeof(Node));
newNode->data=i;
newNode->next=NULL;
ptr->next=newNode;
ptr=newNode;
}
return head;
}
//打印链表
void PrintLink(LinkList head)
{
LinkList ptr;
int nCount=0;
ptr=head;
while(ptr!=NULL)
{
printf("%d ",ptr->data);
ptr=ptr->next;
nCount++;
if(nCount>=20)
{
break;
}
}
printf("\n");
}
//判断链表否"环",确定"环"入口点
LinkList CheckLinkLoop(LinkList head)
{
LinkList fast;
LinkList slow;
int isLoop=0;
fast=head;
slow=head;
while(fast != NULL && fast->next != NULL)
{
//fast每走两步,slow每走步
//两指针相等,表示链表"环"
slow=slow->next;
fast=fast->next->next;
if(fast == slow)
{
isLoop=1;
break;
}
}
if(isLoop==1) //"环"
{
//slow指向链表,fast指向相遇点,两指针每都走步
//两指针第相等,环入口点
slow=head;
while(slow != fast)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
else //没"环"
{
return NULL;
}
}
//计算环
int GetLoopSize(LinkList entryNode)
{
LinkList ptr;
int nCount=0;
ptr=entryNode->next;
nCount++;
while(ptr!=entryNode)
{
nCount++;
ptr=ptr->next;
}
return nCount;
}
int main()
{
LinkList head_1;
LinkList head_2;
LinkList ret_1;
LinkList ret_2;
int loopSize_1;
int loopSize_2;
head_1=CreateLinkWithLoop(); //创建链表("环")
printf("链表1:\n");
PrintLink(head_1); //打印链表
ret_1=CheckLinkLoop(head_1);
if(ret_1!=NULL)
{
printf("环入口点: %d\n",ret_1->data);
loopSize_1=GetLoopSize(ret_1);
printf("环: %d\n",loopSize_1);
}
else
{
printf("链表没环\n");
}
head_2=CreateLink(); //创建链表(没"环")
printf("\n链表2:\n");
PrintLink(head_2); //打印链表
ret_2=CheckLinkLoop(head_2);
if(ret_2 != NULL)
{
printf("环入口点: %d\n",ret_2->data);
loopSize_2=GetLoopSize(ret_2);
printf("环: %d\n",loopSize_2);
}
else
{
printf("链表没环\n");
}
return 0;
}
