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

时间: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