带环链表
这里的带环单链表可不是环形单链表,这个环可能是我们不想要的,所以需要检测。 我们就不假设有一个打结状的环了,那样跑到哪里去也不清楚,这里的“带环链表”,环必然是在末端。 这是经典问题,方法众多,但方法效率差别很大,本文试举三例,并对较优算法加以编程实现。
算法一:暴力查重双指针即可,前一个指针在遍历单链表,后一个指针遍历前指针之前的所有结点是否有与前指针相同的结点。 如果能跑到结尾,自然是无环的,否则就跑下去,总会发现的。 这算法很暴力,不好。
算法二:HashSet查重不需要双指针,但需要多费一些空间,建一个HashSet,里面装每一个搜索过的结点,搜到的结点如果Set里有,就是说明了有环,否则就把新搜到的结点加入HashSet里面。搜到尽头就是没环。
算法三:双指针前一个指针一次跳两个结点,后一个结点一次跳一个结点,如果有环,则前后必能相遇。如果前者跑到尽头就说明没环。
算法核心代码(Java语言描述):
private boolean isCircular