链表环状检测主要有三种方法

时间：2022-07-30 16:50:59
链表环状检测主要有三种方法:
 
  1、追赶法；如   robinzsy。  
  2、外部记录法；如improgrammer。  
  3、内部记录法（打记号）；如VivianSnow。  
 
内部标记法和外部标记法其实是一个道理,不过就是辅助变量一个是在链表节点内,一个是借助辅助数组或者hash或者AVL,红黑树,把已经访问过的节点地址存起来,每次访问下一个时候做查询处理.
 
 
 
追赶法,利用最大公倍数原理,用2个游标,对链表进行访问,例如:p1,p2, p1访问每步向前进1个节点,p2则每次向前前进2个节点,如果有环则p1,p2必会相遇,如果p2先遇到了NULL节点,则说明没有环.
 
关于这个解法最形象的比喻就是在操场当中跑步，速度快的会把速度慢的扣圈可以证明，p2追赶上p1的时候，p1一定还没有走完一遍环路，p2也不会跨越p1多圈才追上我们可以从p2和p1的位置差距来证明，p2一定会赶上p1但是不会跳过p1的因为p2每次走2步，而p1走一步，所以他们之间的差距是一步一步的缩小，4，3，2，1，0 到0的时候就重合了根据这个方式，可以证明，p2每次走三步以上，并不总能加快检测的速度，反而有可能判别不出有环
 
比如，在环的周长L是偶数的时候，初始p2和p1相差奇数的时候，p2每次走三步，就永远和p1不重合，因为他们之间的差距是：  5， 3 ， 1，  L－1， L－3
 
 
 
如何找到环路的入口? 是这里要重点说明的内容：
 
解法如下： 当p2按照每次2步，p1每次一步的方式走，发现p2和p1重合，确定了单向链表有环路了.接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当p1和p2再次相遇的时候，就是环路的入口了。这点可以证明的：
 
在p2和p1第一次相遇的时候，假定p1走了n步骤，环路的入口是在p步的时候经过的，那么有
 
p1走的路径： p+c ＝ n；         c为p1和p2相交点，距离环路入口的距离
 
p2走的路径： p+c+k*L = 2*N；   L为环路的周长，k是整数
 
显然，如果从p+c点开始，p1再走n步骤的话，还可以回到p+c这个点, 同时p2从头开始走的话，经过n不，也会达到p+c这点
 
显然在这个步骤当中p1和p2只有前p步骤走的路径不同，所以当p1和p2再次重合的时候，必然是在链表的环路入口点上。

　　

数据结构-链表环
#include<stdio.h>
#include<stdlib.h>

#define N 3

typedef int datatype;

typedef struct _node_
{
    datatype data;
    struct _node_ *next;
}linknode,*linklist;

linklist creat_empty_linklist()
{
    linklist h;

    h = (linklist)malloc(sizeof(linknode));
    h->next = NULL;

    return h;
}

int empty_linklist(linklist h)
{
    return NULL == h->next;
}

int lenth_linklist(linklist h)
{
    int len = 0;

    linklist p;

    p = h->next;
    //p = h;
    while(p != NULL)
    {
        len++;
        p = p->next;
    }

    return len;
}

void visit_linklist(linklist h)
{
    linklist p;
    
    printf("The linklist is :");
    p = h->next;
    while(p != NULL)
    {
        printf("%d->",p->data);
        p = p->next;
    }

    printf("\b\b    \n");    

    return ;
}

int insert_linklist_1(linklist h,datatype x,int pos)
{
    int i;
    linklist p, q;
    
    p = h;
    if((pos < 0) || (pos > lenth_linklist(h)))  return -1;

    q = (linklist)malloc(sizeof(linknode));
    q->data = x;

    while(pos--)  p = p->next;

    q->next = p->next;
    p->next = q;

    return 0;
}

void insert_linklist_2(linklist h, datatype x)
{
    linklist p, q;

    p = h;
    while((p->next != NULL) && (p->next->data <x))    p = p->next;

    q = (linklist)malloc(sizeof(linknode));
    q->data = x;

    q->next = p->next;
    p->next = q;

    return ;
}

int delete_linklist_1(linklist h, int pos)
{
    linklist p, q;

    p = h;
    if((pos < 0) || (pos >= lenth_linklist(h)))    return -1;

    while(pos--)    p = p->next;

    q = p->next;
    p->next = q->next;
    free(q);

    return 0;
}

int delete_linklist_2(linklist h, datatype x)
{
    linklist p, q;

    q = h;
    p = q->next;
    while(p != NULL){
        if(p->data == x){
            q->next = p->next;
            free(p);
            p = q->next;
        }
        else{
            q = q->next;
            p = q->next;
        }
    }
}

void clear_linklist(linklist h)
{
   linklist p, q;

   q = h;
   p = q->next;
   if(!empty_linklist(h)){
           while(p != NULL){
            q->next = p->next;
            free(p);
            p = q->next;
        }
   }
}

void reverse_linklist(linklist h)
{
    linklist p, q;

    p = h->next;
    h->next = NULL;
    while(p != NULL){
        q = p;
        p = p->next;
        q->next = h->next;
        h->next = q;
    }
}

int main()
{
    int i;
    linklist h, p;

    h = creat_empty_linklist();

    for(i=0; i<8; i++)
        insert_linklist_1(h, i+1, i);
    visit_linklist(h);

    p = h->next;
    while(h->next != NULL)    h = h->next;
    h->next = p;
    h = p;

    printf("MY Josephus : ");
    for(i=0; i<10; i++){
        printf("%d->", p->data);
        p = p->next;
    }
    printf("\b\b    \n");

    p = h;
    printf("My Josephus out is : ");

    while(p != p->next)
    {
        for(i=0; i<N-2; i++)
        {
            p = p->next;
        }
        h = p->next;
        p->next = h->next;
        printf("%d->", h->data);
        free(h);
        p = p->next;
    }
    printf("%d\n", p->data);

    return 0;
}

　

求有环单链表中的环长、环起点、链表长
求有环单链表中的环长、环起点、链表长
1.判断单链表是否有环

　　使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步，指针fast每次走2步。如果存在环，则指针slow、fast会相遇；如果不存在环，指针fast遇到NULL退出。

　　就是所谓的追击相遇问题：

　　　　

2.求有环单链表的环长

 　　在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。

　　设从第一次相遇到第二次相遇，设slow走了len步，则fast走了2*len步，相遇时多走了一圈：

　　　　环长=2*len-len。

3.求有环单链表的环连接点位置

　　第一次碰撞点Pos到连接点Join的距离=头指针到连接点Join的距离，因此，分别从第一次碰撞点Pos、头指针head开始走，相遇的那个点就是连接点。

 　　　　

　　在环上相遇后，记录第一次相遇点为Pos，连接点为Join，假设头结点到连接点的长度为LenA，连接点到第一次相遇点的长度为x，环长为R。

　　　　第一次相遇时，slow走的长度 S = LenA + x;

　　　　第一次相遇时，fast走的长度 2S = LenA + n*R + x;

　　　　所以可以知道，LenA + x =  n*R;　　LenA = n*R -x;

4.求有环单链表的链表长

 　　上述2中求出了环的长度；3中求出了连接点的位置，就可以求出头结点到连接点的长度。两者相加就是链表的长度。

 

编程实现：

　　下面是代码中的例子：

　　

　　具体代码如下：

 View Code
　　执行结果：



本文网址：http://www.cnblogs.com/xudong-bupt/p/3667729.html

参考网址：http://blog.sina.com.cn/s/blog_725dd1010100tqwp.html

　　

　

标签：

相关文章