[数据结构与算法] 判断单链表是否环化和寻找环的起点

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 判断单链表是否环化和寻找环的起点 -> 正文阅读

[数据结构与算法]判断单链表是否环化和寻找环的起点

首先判断链表是否环化

我们可以使用一对"快慢指针",快指针每次走两步,慢指针每次走一步,同时从起点出发,依次向后遍历链表,如果两个指针相遇则一定存在环,如果不能相遇则不存在环

实现代码

 LNode *fast=L->next,*slow=L->next;//使用快慢指针
    while(fast!=NULL&&fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;//快指针每次走两步,慢指针每次走一步
        if(slow==fast)break;//在x处相遇相遇
    }
    if(slow==NULL||fast->next==NULL)return NULL;//判断是否环化

寻找环的起点

在这里插入图片描述

整体实现代码

#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>

typedef int Elemtype;

typedef struct LNode
{
    Elemtype data;
    struct  LNode *next;
} LNode,*LinkList;




LinkList List_TailInsert(LinkList L)
{
    int x;
    L=(LinkList)malloc(sizeof(LinkList));//创建头节点
    L->next=NULL;

    LNode *r=L,*s;
    scanf("%d",&x);
    while(x!=9999)
    {
        s=(LNode*)malloc(sizeof(LNode*));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=L->next; //使环化
    return L;
}



void PrintLinkList(LinkList L)
{
    printf("打印链表\n");
    LNode *r=L->next;
    while(r!=NULL)
    {
        printf("%d--->",r->data);
        r=r->next;
    }
    printf("\n");
}


LNode * FindLoopStart(LinkList L)
{
    LNode *fast=L->next,*slow=L->next;//使用快慢指针
    while(fast!=NULL&&fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;//快指针每次走两步,慢指针每次走一步
        if(slow==fast)break;//在x处相遇相遇
    }
    if(slow==NULL||fast->next==NULL)return NULL;//判断是否环化

    LNode *p1=L->next,*p2=slow;//p2为相遇点
    while(p1!=p2)
    {
        p1=p1->next;
        p2=p2->next;
    }
    return p1;
}


int main()
{

    LinkList L;//头指针,创建链表
    printf("创建链表,输入链表的值 9999表示结束!\n");
    L=List_TailInsert(L);
    printf("链表环起点的值为  %d\n",FindLoopStart(L)->data);

    return 0;
}