数据结构--链表--单链表中环的检测，环的入口，环的长度的计算_(求链表中环的长度)

就如数字6一样的单链表结构，如何检测是否有6下部的○呢，并且求交叉点位置

思路

1. 使用快慢指针（一个一次走2步，一个走1步），若快慢指针第一次相遇，则有环
   慢指针路程 $s=a+b$
   快指针路程 $2s=a+b+n\ast R$
   $s=n\ast R$
   链表的长度 $L=a+b+c=n\ast R+c$
   又 $L=a+R$
   则 $n\ast R+c=a+R\Rightarrow (n-1)\ast R+c=a$
   意味着从head开始走到入口 $a$ 步 == 从第一次相遇点走 $n-1$ 圈 + 再走 $c$ 步

2. 由上可以使快慢指针第一次到达相遇点时，使慢指针回到head，快指针仍在相遇点，然后两人步伐一致，最后会在入口相见。

C++代码实现：

完整代码见：https://github.com/hitskyer/course/tree/master/dataAlgorithm/chenmingming/linkedList

类实现函数

bool SingleList::hasLoop()
{
    bool loop = false;
    ListNode fast = m_pHead, slow = m_pHead;
    ListNode posMeet = m_pHead, ringEntrance = m_pHead;//环的可能的入口应初始化成head
    if(m_pHead == NULL)
    {
        loop = false;
        std::cout << "list has no loop!" << std::endl;
    }
    else
    {
        while(fast && fast->pNext)
        {
            fast = fast->pNext->pNext;
            slow = slow->pNext;
            if(fast == slow)
            {
                loop = true;
                posMeet = fast; //第一次相遇的地方
                break;
            }
        }
        slow = m_pHead; 
        //接着让慢指针回到表头（这里是关键），继续一起同步前行，第二次相遇的地方为环的入口
        while(slow != fast)
        {
            slow = slow->pNext;
            fast = fast->pNext;
            if(fast == slow)
                ringEntrance = fast;
        }
        size_t lenOf_headToEntrance = howManyNode(m_pHead,ringEntrance);
        size_t ringLen_1 = howManyNode(ringEntrance->pNext, ringEntrance);
        std::cout << "len of head to ring entrance is " << lenOf_headToEntrance << std::endl;
        std::cout << "entrance Node is " << ringEntrance->data << std::endl;
        std::cout << "len of ring is " << ringLen_1 + 1 << std::endl;
        std::cout << "len of List is " << lenOf_headToEntrance + ringLen_1 + 1 << std::endl;
    }
    return loop;
}

size_t SingleList::howManyNode(ListNode ps, ListNode pe)	
	//计算两个指针之间有多少个节点（不包含第二个参数处的节点）
{
    size_t count = 0;
    while(ps != pe)
    {
        ps = ps->pNext;
        ++count;
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

singleListIsLoop.cpp主函数

//
// Created by mingm on 2019/3/24.
//检查单链表中是否存在环，求环的长度，链表长度，及环的入口
#include <iostream>
#include <time.h>
#include <cstdlib>
#include "./homework/singleList.cpp"
using namespace std;
int main()
{
    srand((unsigned)time(NULL));    //用时间随机数种子
    size_t len = 10;       //测试链表最大长度
    for(size_t j = 1; j < len; ++j)
    {
        SingleList intList;
        for(size_t i = 0; i < j; ++i)
        {
            intList.AddTail(rand()%100);    //添加随机数到链表
        }
        cout << "no loop list: " << endl;
        intList.PrintList();    //排序前链表打印
        size_t n = rand()%(intList.GetLength());    //0-链表减1的随机数
        ListNode randNode = intList.GetHeadNode();
        for(size_t i = 0; i != n; ++i)
        {
            randNode = randNode->pNext;     //链表的一个随机节点
        }
        ListNode originTail = intList.GetTailNode();
        originTail->pNext = randNode;    //尾节点接入链表中的随机位置形成环
        intList.hasLoop();  //调用环检测函数
        originTail->pNext = NULL;   //断开环，让链表能够按照单链表析构函数析构!!!!!!!
        std::cout << "getListLength（） is " << intList.GetLength() << std::endl;
        std::cout << "-----------------------------------------" << std::endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

Valgrind检测结果

从链表长度1开始测试到9，测试结果均正确！