专栏首页机器学习从入门到成神判断单链表是否有环的两种方法

判断单链表是否有环的两种方法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/54745408

如图,如果单链表有环,则在遍历时,在通过6之后,会重新回到3,那么我们可以在遍历时使用两个指针,看两个指针是否相等。


方法一:使用p、q两个指针,p总是向前走,但q每次都从头开始走,对于每个节点,看p走的步数是否和q一样。如图,当p从6走到3时,用了6步,此时若q从head出发,则只需两步就到3,因而步数不等,出现矛盾,存在环

方法二:使用p、q两个指针,p每次向前走一步,q每次向前走两步,若在某个时候p == q,则存在环。

代码如下:

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

#define LEN 8
typedef struct node* node_t;

struct node{  
    char val;  
    struct node *next;  
};  

//method 1
int has_loop(struct node *head);
//method 2
int has_loop2(node_t head);

int main()
{
    node_t* arr = (node_t*)malloc(sizeof(struct node)*LEN);
    arr[0] = (node_t)malloc(sizeof(struct node));
    int i;
    for(i = 1; i < LEN; i++)
    {
        arr[i] = (node_t)malloc(sizeof(struct node));
        arr[i - 1]->next = arr[i];
    }
    arr[LEN - 1]->next = NULL;

    //you can add a loop here to test
    //arr[6]->next = arr[0];
    if (has_loop(arr[0]))
        printf("method1: has loop.\n");
    else
        printf("method1: has no loop.\n");

    if (has_loop2(arr[0]))
        printf("method2: has loop.\n");
    else
        printf("method2: has no loop.\n");

    return 0;
}

//if two pointer are equal, but they don't have the same steps, then has a loop
int has_loop(node_t head)  
{  
    node_t cur1 = head;  
    int pos1 = 0;  
    while(cur1){  
        node_t cur2 = head;  
        int pos2 = 0;  
        pos1 ++;  
        while(cur2){  
            pos2 ++;  
            if(cur2 == cur1){  
                if(pos1 == pos2)  
                    break;  
                else  
                    return 1;
            }  
            cur2 = cur2->next;  
        }  
        cur1 = cur1->next;  
    }  
    return 0;  
} 

//using step1 and step2 here 
//if exists a loop, then the pointer which use step2 will catch up with the pointer which uses step1
int has_loop2(node_t head)
{
    node_t p = head;
    node_t q = head;
    while (p != NULL && q != NULL)
    {
        /*
        p = p->next;
        if (q->next != NULL)
            q = q->next->next;
        if (p == q)
            return 1;
            */
        //correct it on 17/11/2012
        p = p->next;
        q = q->next;
        if (q != NULL)
            q = q->next;
        if (p != NULL && p == q)
            return 1;
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Webpack创建、运行vue.js项目及其目录结构详解

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

    大黄大黄大黄
  • Keras-RetinaNet训练自己的数据详细教程

    1、代码开源框架使用的是 fizyr/keras-retinanet 2、Keras版本要2.2.4以上

    大黄大黄大黄
  • 深入理解并发/并行,阻塞/非阻塞,同步/异步

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

    大黄大黄大黄
  • Generator的正确打开方式

    贾顺名
  • 子字符串查找----KMP算法

    SuperHeroes
  • Generator的正确打开方式

    代码运行后,我们首先会得到一条cooking的log, 然后在3s后会再次得到一条log。

    贾顺名
  • python高级特性-生成器

    在每次调用next()的时候执行,遇到yield语句返回,再次执行时从上次返回的yield语句处继续执行。

    yaohong
  • LeetCode 1290. Convert Binary Number in a Linked List to Integer

    ShenduCC
  • BZOJ1969: [Ahoi2005]LANE 航线规划(LCT)

    attack
  • Top K问题

    如果你对上述两者的原理有所了解,可以继续往下看.如果不了解,可以点击链接先看一下基础~.

    呼延十

扫码关注云+社区

领取腾讯云代金券