解决单链表中的环问题

给定一个单链表，只给出头指针h：

如何判断是否存在环？
如何知道环的长度？
如何找出环的连接点在哪里？
带环链表的长度是多少？

问题1 如何判断是否有环

使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。

问题2 如何判断环的长度

在相遇点出同时出发，fast指针和slow指针再次相遇时，slow指针走过的点的个数就是环的长度。试问会不会slow在不到一圈的地方两者相遇呢？不会，因为假设slow走s,则fast走2s。二者相遇则二者距离必相差圈数的倍数，即：2s-s = k*圈距离=s。此时k=1。因此得出结论：从相遇到再次相遇，slow再走完整的一圈。

问题3 如何找出环的连接点

定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。

证明：

链表形状类似数字6。
假设甩尾（在环外）长度为 a（结点个数），环内长度为 b 。
则总长度（也是总结点数）为 a+b 。
从头开始，0 base 编号。
将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ...
当 i＜a 时，S(i)=i ；
当 i≥a 时，S(i)=a+(i-a)%b 。

分析追赶过程。
两个指针分别前进，假定经过 x 步后，碰撞。则有：S(x)=S(2x)
由环的周期性有：2x=tb+x 。得到 x=tb 。
另，碰撞时，必须在环内，不可能在甩尾段，有 x>=a 。

连接点为从起点走 a 步，即 S(a)。
S(a) = S(tb+a) = S(x+a)。
得到结论：从碰撞点 x 前进 a 步即为连接点。

根据假设易知 S(a-1) 在甩尾段，S(a) 在环上，而 S(x+a) 必然在环上。所以可以发生碰撞。又，同为前进 a 步，同为连接点，所以必然发生碰撞。

综上，从 x 点和从起点同步前进，第一个碰撞点就是连接点。

问题4 带环链表的长度是多少

问题2知道环的长度，问题3知道环外边的长度。两者相加即为总长度。

参考代码

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

typedef struct node
{
  int data;
  struct node *next;
}node;

node *Create_list()   //建立链表
{
  node *p_return, *p;
  p_return = NULL;

  node *n1 = (node *)malloc(sizeof(node));
  n1->data = 1;
  n1->next = NULL;
  p = n1;
  p_return = p;

  node *n2 = (node *)malloc(sizeof(node));
  n2->data = 2;
  n2->next = NULL;
  p->next = n2;
  p = n2;

  node *n3 = (node *)malloc(sizeof(node));
  n3->data = 3;
  n3->next = NULL;
  p->next = n3;
  p = n3;

  node *n4 = (node *)malloc(sizeof(node));
  n4->data = 4;
  n4->next = NULL;
  p->next = n4;
  p = n4;

  node *n5 = (node *)malloc(sizeof(node));
  n5->data = 5;
  n5->next = NULL;
  p->next = n5;
  p = n5;

  node *n6 = (node *)malloc(sizeof(node));
  n6->data = 6;
  n6->next = NULL;
  p->next = n6;
  p = n6;

  p->next = n3;

  return p_return;
}

node *find_in_node(node *p1, node *p2)   //找到入环的结点
{
  while(p1 != p2)
  {
    p1 = p1->next;
    p2 = p2->next;
  }
  return p1;
}
int get_out_len(node *p1, node *p2)   //计算出环外边的长度
{
  int num = 0;
  while(p1 != p2)
  {
    p1 = p1->next;
    p2 = p2->next;
    num++;
  }
  return num;
}

node *check_loop(node *p)  //检查是否有环
{
  node *p_slow, *p_fast;
  p_slow = p;
  p_fast = p;
  int tag = 0;
  while(p_slow && p_fast->next)
  {
    p_slow = p_slow->next;
    p_fast = p_fast->next->next;
    if(p_slow == p_fast)
    {
      tag = 1;
      break;
    }
  }
  if(tag == 1)
  {
    printf("Have loop\n");
    return p_slow;
  }
  else
  {
    printf("Not have loop\n");
    return NULL;
  }
}
int get_len_loop(node *var_loop)   //得出环的长度
{
  node *p = var_loop->next;
  int num = 1;
  while(p != var_loop)
  {
    p = p->next;
    num++;
  }
  return num;
}

int main()
{
  node *p = Create_list();
  node *coin_loop = check_loop(p);
  if(coin_loop)
  {
    int len_loop = get_len_loop(coin_loop);
    printf("Length of Loop is:%d\n", len_loop);
    node *in_node = find_in_node(p, coin_loop);
    int len_out = get_out_len(p, coin_loop);
    printf("Length of out Loop is %d\n", len_out);
    printf("Length of all is %d\n", len_out + len_loop);
  }
}

秒客网

解决单链表中的环问题

相关文章