网络建设网站有关知识,成都网页设计招聘,wordpress评论回复通知,优化关键词首页排行榜141.环形链表 目录 141.环形链表一、哈希表二、双指针 一、哈希表
最容易想到的方法就是遍历所有节点#xff0c;每次遍历到一个节点的时候#xff0c;判断该节点此前是否被访问过
我们可以使用哈希表来存储所有已经访问过的节点
每次到达一个节点#xff0c;如果该节点已…141.环形链表 目录 141.环形链表一、哈希表二、双指针 一、哈希表
最容易想到的方法就是遍历所有节点每次遍历到一个节点的时候判断该节点此前是否被访问过
我们可以使用哈希表来存储所有已经访问过的节点
每次到达一个节点如果该节点已经存在于哈希表中则说明该链表是环形链表否则就将该节点加入到哈希表中重复这一操作直到遍历完整个链表为止
值得一提的是这里我们使用HashSetSet集合的特点是什么即该集合中不会出现重复的元素如此一来就很好判断了 public boolean hasCycle(ListNode head) {SetListNode set new HashSetListNode();while(head!null){//如果向哈希Set中加入节点失败即该Set中已经有了重复的元素if(!set.add(head)){return true;}head head.next;}return false;}二、双指针
本题的快慢指针法需要我们先了解一下Floyd判圈算法龟兔赛跑算法
假设乌龟和兔子从链表上同一节点开始移动兔子跑得快乌龟跑得慢如果链表中没有环那么兔子将一直处在乌龟的前方
如果链表中有环那么兔子会先于乌龟进入环并一直在环中移动等到乌龟进入环后由于兔子的速度快于乌龟所以兔子一定会在某个时刻追上乌龟 可以根据这个思路来解决这个问题我们定义两个指针一快一慢。慢指针每次只移动一步而快指针每次移动两步
初始时慢指针在head位置快指针在head.next位置
这样一来如果在移动的过程中快指针反过来追上慢指针就说明该链表为环形链表
否则快指针将到达链表尾部该链表不为环形链表 public boolean hasCycle(ListNode head) {if(headnull||head.nextnull){return false;}ListNode slow head;ListNode fast head.next;while(slow!fast){if(fastnull||fast.nextnull){return false;}slow slow.next;fast fast.next.next;}return true;}
