一、题目描述
如果有一个单向链表，链表当中有可能出现＂环＂，就像下图这样，如何判断这个链表是有环链表？
二、解题思路
方案一：暴力法
从头节点，依次遍历单链表的每一个节点，每到一个新的节点就头节点重新遍历之前的所有的节点，对比此时的节点，如果相同，证明该节点遍历过两次，以此说明链表是有环的
Node p = head.next while(p.next!==null){ Node c = head while(c!==p){ c=c.next } if(c.next!==p.next){ return true } p = p.next } return false; 此方案时间复杂度为Ｏ（ｎ＾２），空间复杂度为 O(1)
第二种方案：用 hashMap 缓存遍历的过的节点
还是头节点进行遍历，每一次遍历新的节点时，对比存储到 hashMap 集合是否有相同的节点，有，证明有环，无，存储到集合中
伪代码：
Node p = head HashMap hm = new HashMap()<Node,Node> while(p!=null){ if(hm.get(p)){ return true } hm.put(p,p) p =p.next } 第三种方案：双指针遍历
首先创建两个指针 1 和 2，同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针 1 每次向下移动一个节点，让指针 2 每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环
伪代码：
Node p = head Node q = head.next while(p!==q){ if(p.next==null) return false p =p.next if(q.next==null) return false if(q.next.next==null) return false q = q.next.next } return true 此方案的时间复杂度为 O(n),空间复杂度为 O(1)
作者简介
考拉后端开发小哥 Rowland,热爱运动还有点萌！
2
Select Language