《C语言单向链表环测试并返回环起始节点》由会员分享，可在线阅读，更多相关《C语言单向链表环测试并返回环起始节点（5页珍藏版）》请在金锄头文库上搜索。
1、C 语言单向链表环测试并返回环起始节点有时候我们需要测试一个单向链表是否存在环。最土鳖的方法就是改变链表的数据结构，给每个节点添加一个 bool 变量，在未测试时全部初始化为 false，然后遍历链表，每访问一个节点，先测试其 bool 成员来确定这个节点是否被访问过，如果为 true，则表示访问过，则有环，否则设置 bool 成员为 true，表明访问过，然后继续测试。如果不改变数据结构的话，我们有以下的解决方案：1. 测试是否有环：我们可以构建两个迭代器来遍历链表，一个每一次移动一个节点，另外一个每次移动两个节点。如果这两个一快一慢的土鳖迭代器相遇了，也就是说他们在某个时刻都到了同一个节点
2、，那么我们可以肯定有环存在。直观的理解就是让两个土鳖一快一慢在 400 米环形跑道上各选一个位置，然后同时顺时针做死了跑，那么这两个土鳖总能相遇,因为一个比另外一个快。如果需要严谨的证明，我们可以这样理解。假设在某个迭代时刻，两个土鳖迭代器（以后简称土鳖）都进入了环，一个距环起始点为 i，一个距环起始点为 j。这个假设必然有成立的时候，因为跑着跑着他们总会进入环，而且一旦进入那就出不来了，只能做死了跑。然后假设又跑了一会儿，这两个土鳖相遇了，一个土鳖跑了 x 步，一个跑了 2x 步。如果这个环总共长 n,也就是说慢土鳖需要跑 n 步才能跑完一圈。然后我们可以得出 i+x 和j+2x 对于 n
3、同余，也就是说 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。一个显然的事实是，当两
4、个土鳖相遇时，慢土鳖跑过的路径是快土鳖的一半。这样的话，在相遇前，当慢土鳖跑了一般的时候，快土鳖已经经过了相遇点（落脚或者跨越）。这样的话当慢土鳖跑完后半段的时候，快土鳖从相遇点开始又跑了同样的路程到达了相遇点，这个路程的长度等于慢土鳖总共跑的长度。现在牛逼的地方来了，如果慢土鳖从头开始跑的时候，有另外一个慢土鳖从相遇点 cross 开始跑，那么他们两个也会在相遇点相遇，我们称这两个土鳖分别为 A 和 B。土鳖 B 走的路程和快土鳖后半段时间走过的路程是完全一样的，唯一的区别就是他慢一点而已。现在第二个牛逼的地方来了，因为慢土鳖 A 和 B 的速度是一样的，那么他们在相遇点之前的节奏也是一样的
5、，也就是说他们在相遇点值钱已经相遇了，而且一同样的速度相伴走到了相遇点 cross。他们从什么时候相遇开始这段快乐的旅程呢，当然是环起始点 start。我们可以让慢土鳖 A 和B 从相遇点倒退，这样就能理解为什么他们在 start 点相遇了。OK，现在我们有了解决方案，让慢土鳖 A 从链表头 start 开始跑，让另外一个慢土鳖从相遇点 cross 开始跑，他们第一次的相遇点就是环起始点。大功告成，标点符号（废话）有点多，大家不要介意。下面是 C+代码：1 #include 2 #include 34 template5 struct Node6 7 T value;8 Node* next;
6、9 ;1011 /Test if a linked list has circle12 template13 bool hasLoop(Node* linkedList, Node* loopCross = NULL)14 15 /empty linked list, no circle16 if(linkedList = NULL | loopCross = NULL) return false;1718 Node* slowWalker = linkedList;19 Node* quickWalker = linkedList;20 while(quickWalker != NULL &
7、 quickWalker-next != NULL)21 22 / move the walker23 slowWalker = slowWalker-next; /one each step24 quickWalker = quickWalker-next-next; /two each step25 if(slowWalker = quickWalker)26 27 /has circle28 *loopCross = slowWalker;29 return true;30 31 3233 return false;34 3536 /Get the loop start node37 t
8、emplate38 Node* getLoopStart(Node* linkedList, Node* loopCross)39 40 Node* startFromHead = linkedList;41 Node* 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 != startFromCros
9、s)45 46 startFromHead = startFromHead-next;47 startFromCross = startFromCross-next;48 49 return startFromHead;50 5152 int main()53 54 Node* linkedList = new Node();55 linkedList-value = 0;56 linkedList-next = NULL;5758 Node* pNode = linkedList;59 Node* crossNode = NULL;6061 for(int i = 1; i * tem =
10、new Node();64 tem-value = i;65 tem-next = NULL;6667 pNode-next = tem;68 pNode = tem;69 / set the cross node;70 if(i = 66)71 crossNode = tem;72 7374 printf(test normal linked list:n);75 if(hasLoop(linkedList)76 printf(has circle.n);77 else78 printf(no circle.n);7980 printf(test circle linked list:n);
11、81 pNode-next = crossNode; / Create a circle8283 Node* loopCross = NULL;84 if(hasLoop(linkedList, &loopCross)85 86 printf(has circle.n);87 Node* loopStart = getLoopStart(linkedList, loopCross);88 if(loopStart != NULL)89 printf(the value of the circle start node is %dn, loopStart-value);90 91 else92 printf(no circle.);93
