您的位置: 首页 > 软件教程 > C语言教程专题 > C语言单向链表环测试并返回环起始节点

C语言单向链表环测试并返回环起始节点

8.3分
出处:网络 时间:2011-06-27

您可能感兴趣的话题: C语言  

核心提示:有时候我们需要测试一个单向链表是否存在环。最土鳖的方法就是改变链表的数据结构,给每个节点添加一个bool变量

  有时候我们需要测试一个单向链表是否存在环。最土鳖的方法就是改变链表的数据结构,给每个节点添加一个bool变量,在未测试时全部初始化为false,然后遍历链表,每访问一个节点,先测试其bool成员来确定这个节点是否被访问过,如果为true,则表示访问过,则有环,否则设置bool成员为true,表明访问过,然后继续测试。

  如果不改变数据结构的话,我们有以下的解决方案:

  1. 测试是否有环:

  我们可以构建两个迭代器来遍历链表,一个每一次移动一个节点,另外一个每次移动两个节点。如果这两个一快一慢的土鳖迭代器相遇了,也就是说他们在某个时刻都到了同一个节点,那么我们可以肯定有环存在。直观的理解就是让两个土鳖一快一慢在400米环形跑道上各选一个位置,然后同时顺时针做死了跑,那么这两个土鳖总能相遇,因为一个比另外一个快。

  如果需要严谨的证明,我们可以这样理解。假设在某个迭代时刻,两个土鳖迭代器(以后简称土鳖)都进入了环,一个距环起始点为i,一个距环起始点为j。这个假设必然有成立的时候,因为跑着跑着他们总会进入环,而且一旦进入那就出不来了,只能做死了跑。然后假设又跑了一会儿,这两个土鳖相遇了,一个土鳖跑了x步,一个跑了2x步。如果这个环总共长n,也就是说慢土鳖需要跑n步才能跑完一圈。然后我们可以得出i+x和j+2x对于n同余,也就是说i+x和j+2x除以n的余数是相同的,写成同余等式就是(i+x)=j+2x(mod n) ,根据同余加减法性质,我们可以让上面的式子减去x=x(mod m),得到i=(j+x)(mod m)。因为x未知,所以上面的式子是个同余方程,i、j都是普通整数,很明显这个方程是有解的。例如2=(1+x)(mod 5)的一个简单解就是1。所以这两个土鳖跑着跑着总会相遇。也就是说我们上面检测环的算法可行,不会死循环。

  2. 获取环起始点:

  基于问题1的分析,快土鳖和慢土鳖总会在某个节点相遇,假设这个点为cross。同事假设环起始点为start。一个显然的事实是,当两个土鳖相遇时,慢土鳖跑过的路径是快土鳖的一半。这样的话,在相遇前,当慢土鳖跑了一般的时候,快土鳖已经经过了相遇点(落脚或者跨越)。这样的话当慢土鳖跑完后半段的时候,快土鳖从相遇点开始又跑了同样的路程到达了相遇点,这个路程的长度等于慢土鳖总共跑的长度。现在牛逼的地方来了,如果慢土鳖从头开始跑的时候,有另外一个慢土鳖从相遇点cross开始跑,那么他们两个也会在相遇点相遇,我们称这两个土鳖分别为A和B。土鳖B走的路程和快土鳖后半段时间走过的路程是完全一样的,唯一的区别就是他慢一点而已。现在第二个牛逼的地方来了,因为慢土鳖A和B的速度是一样的,那么他们在相遇点之前的节奏也是一样的,也就是说他们在相遇点值钱已经相遇了,而且一同样的速度相伴走到了相遇点cross。他们从什么时候相遇开始这段快乐的旅程呢,当然是环起始点start。我们可以让慢土鳖A和B从相遇点倒退,这样就能理解为什么他们在start点相遇了。OK,现在我们有了解决方案,让慢土鳖A从链表头start开始跑,让另外一个慢土鳖从相遇点cross开始跑,他们第一次的相遇点就是环起始点。

  大功告成,标点符号(废话)有点多,大家不要介意。

  下面是C++代码:

  1 #include <stdio.h>

  2 #include <stdlib.h>

  3

  4 template<typename T>

  5 struct Node

  6 {

  7 T value;

  8 Node* next;

  9 };

  10

  11 //Test if a linked list has circle

  12 template<typename T>

  13 bool hasLoop(Node<T>* linkedList, Node<T>** loopCross = NULL)

  14 {

  15 //empty linked list, no circle

  16 if(linkedList == NULL || loopCross == NULL) return false;

  17

  18 Node<T>* slowWalker = linkedList;

  19 Node<T>* quickWalker = linkedList;

  20 while(quickWalker != NULL && quickWalker->next != NULL)

  21 {

  22 // move the walker

  23 slowWalker = slowWalker->next; //one each step

  24 quickWalker = quickWalker->next->next; //two each step

  25 if(slowWalker == quickWalker)

  26 {

  27 //has circle

  28 *loopCross = slowWalker;

  29 return true;

  30 }

  31 }

  32

  33 return false;

  34 }

  35

  36 //Get the loop start node

  37 template<typename T>

  38 Node<T>* getLoopStart(Node<T>* linkedList, Node<T>* loopCross)

  39 {

  40 Node<T>* startFromHead = linkedList;

  41 Node<T>* startFromCross = loopCross;

  42 // Move one pointer from head and move another from the cross node.

  43 // They will meet each other at the loop start node.

  44 while(startFromHead != startFromCross)

  45 {

  46 startFromHead = startFromHead->next;

  47 startFromCross = startFromCross->next;

  48 }

  49 return startFromHead;

  50 }

  51

  52 int main()

  53 {

  54 Node<int>* linkedList = new Node<int>();

  55 linkedList->value = 0;

  56 linkedList->next = NULL;

  57

  58 Node<int>* pNode = linkedList;

  59 Node<int>* crossNode = NULL;

  60

  61 for(int i = 1; i < 100; i++)

  62 {

  63 Node<int>* tem = new Node<int>();

  64 tem->value = i;

  65 tem->next = NULL;

  66

  67 pNode->next = tem;

  68 pNode = tem;

  69 // set the cross node;

  70 if(i == 66)

  71 crossNode = tem;

  72 }

  73

  74 printf("test normal linked list:\n");

  75 if(hasLoop(linkedList))

  76 printf("has circle.\n");

  77 else

  78 printf("no circle.\n");

  79

  80 printf("test circle linked list:\n");

  81 pNode->next = crossNode; // Create a circle

  82

  83 Node<int>* loopCross = NULL;

  84 if(hasLoop(linkedList, &loopCross))

  85 {

  86 printf("has circle.\n");

  87 Node<int>* loopStart = getLoopStart(linkedList, loopCross);

  88 if(loopStart != NULL)

  89 printf("the value of the circle start node is %d\n", loopStart->value);

  90 }

  91 else

  92 printf("no circle.");

  93 }

网友评论
精品软件课程
更多 >
C++是一种静态数据类型检查的,支持多重编程... [详细]
Java,是由Sun Microsystem... [详细]
Visual Basic是一种由微软公司开发... [详细]
Oracle Database,又名Orac... [详细]
Visual Basic.NET是从 Vis... [详细]
Visual C++微软公司的C++开发工具... [详细]