单链表面试题~带环链表的入口点

昨天做了一个小总结，发现单链表这块关于带环链表漏掉了，今天就来总结一下。

要寻找一个单链表的环的入口点，首先得判断一个链表是否带环，那么又怎样判断一个单链表是否带环呢？

首先我们得普及一下环有什么特性，我们知道无环的单链表有首节点和尾节点，那么带环的单链表呢？显然还是有首节点的，但是没有尾节点吧。

如图所示：

带环的单链表既然没有尾结点，那么要是遍历的话，就会无限循环，我们就没法通过这样来判断这是带环的，那么我们就要想一个办法让其停下来。

我们知道，运动会三千米赛跑的时候，第一名总会超过最后一名一圈，他们都是从同一个起点开始跑的，最后跑的快的追上了跑的慢的。这就是圈的特性，那么我们是不是也可以使用这一点来判断单链表是否带环。

我们定义一个快的指针，让其一步走两个节点，再定义一个慢的节点，一步走一个节点，这样，如果链表带环，那么总有一个地方让这两个指针是相遇的；如果不带环那么快的会先到尾结点。

那么接下来就来实现吧：

typedef struct LinkNode  //节点
{  DataType data;  struct LinkNode *next;  
}LinkNode,*pLinkNode; typedef struct LinkList  //链表
{  LinkNode *pHead;  
}LinkList,*pLinkList;  pLinkNode isCircle(pLinkList plist)  //判断是不是带环链表
{  assert(plist);  if (NULL == plist->pHead)  {  printf("链表为空\n");  return NULL;  }  pLinkNode fast = plist->pHead;  pLinkNode slow = plist->pHead;  while (fast && fast->next)  //如果快的指针先到尾结点，那么不是。（奇偶）{  fast = fast->next->next;  slow = slow->next;  if (fast == slow)  //相遇，那么是带环的链表return fast;  }  return NULL;  
}  

判断是不是带环的链表很简单，只要理解了这个过程，没啥问题，那么知道了链表是带环的链表，如何来找带环链表的入口呢？

这涉及不太高深的数学问题，作为数学专业的我，还是很乐意讲解的，首先来看下图：

我们先将一些未知量设出来，这样就可以进行运算了：

首先可以列出一个简单的等式：a+r=L ①

那么再根据两个指针来列一个等式： a+n*r+x=(a+x)*2 ②

解释一下第二个式子：左半部分是快的指针相遇前走的路程首先走了一段 a 之后，在进入环中走了 n 圈，又走了x段路程和慢的指针相遇；慢的指针路程因为它的速度是快的指针的一半，所以时间相同的情况下，快的指针走过的路程当然是慢的指针走过的路程的二倍。

然后联合①、②得：a=n*r-x

这样假设n为1时，即——a=r-x，我们要是再定义一个指针，从表头开始遍历，同时，让慢的指针从相遇点开始，那么当他们相遇的时候，就是入口点的地方。

下面我们来看代码：

pLinkNode firstCrossNode(pLinkList plist)  
{  assert(plist);  if (NULL == plist->pHead)  {  printf("链表是空\n");  return NULL;  } pLinkNode ret = isCircle(plist);  //接收相遇点的指针if (ret == NULL)  {  printf("链表不带环\n");  return NULL;  }   pLinkNode start = plist->pHead;  //从表头开始pLinkNode slow = ret;  //从相遇点开始while (start)  {  start = start->next;  slow = slow->next;  if (start == slow)  return start;  //返回入口点的指针}  
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！