有环链表找环入口 判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？

判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？  

算法思想 先分析是否有环 为此我们建立两个指针 从header一起向前跑 一个步长为 一个步长为 用while（直到步长 的跑到结尾）检查两个指针是否相等 直到找到为止 static bool JudgeCircleExists(Link head) { Link first = head; // step each time Link second = head; // steps each time while (second Next != null &# ;&# ; second Next Next != null) { second = second Next Next; first = first Next; if (second == first) return true; } return false; }

那又如何知道环的长度呢？ 根据上面的算法 在返回true的地方 也就是 个指针相遇处 这个位置的节点P肯定位于环上 我们从这个节点开始先前走 转了一圈肯定能回来 static int GetCircleLength(Link point) { int length = ; Link curr = point; while (curr Next != point) { length++; curr = curr Next; } return length; }

继续我们的讨论 如何找到环的 起始 点呢？ 延续上面的思路 我们仍然在返回true的地方P 计算一下从有环单链表的表头head到P点的距离 static int GetLengthFromHeadToPoint(Link head Link point) { int length = ; Link curr = head; while (curr != point) { length++; curr = curr Next; } return length; }