营销型网站的案例,网站做访问追踪,网站建设开发客户,优品wordpress就如数字6一样的单链表结构#xff0c;如何检测是否有6下部的○呢#xff0c;并且求交叉点位置
思路 使用快慢指针#xff08;一个一次走2步#xff0c;一个走1步#xff09;#xff0c;若快慢指针第一次相遇#xff0c;则有环 慢指针路程 sabs absab 快指针路程 2sa…就如数字6一样的单链表结构如何检测是否有6下部的○呢并且求交叉点位置
思路 使用快慢指针一个一次走2步一个走1步若快慢指针第一次相遇则有环 慢指针路程 sabs absab 快指针路程 2sabn∗R2s abn*R2sabn∗R sn∗Rs n*Rsn∗R 链表的长度 Labcn∗RcL abc n*RcLabcn∗Rc 又 LaRL a RLaR 则 n∗RcaR⇒(n−1)∗Rcan*Rc aR \Rightarrow (n-1)*Rc an∗RcaR⇒(n−1)∗Rca 意味着从head开始走到入口 aaa 步 从第一次相遇点走 n−1n-1n−1 圈 再走 ccc 步 由上可以使快慢指针第一次到达相遇点时使慢指针回到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;//环的可能的入口应初始化成headif(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;
}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;
}Valgrind检测结果 从链表长度1开始测试到9测试结果均正确
