北京建筑工程公司,中山网站的优化,表白时刻网站,昌网站建设环形链表
问题描述
给你一个链表的头节点 head #xff0c;判断链表中是否有环。如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;评测系统内部使用整数 pos 来表示链表尾连接到链表中…环形链表
问题描述
给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 则返回 true 。 否则返回 false 。详见leetcode141
问题分析
最直接的方式就是利用集合来判断遍历链表节点判断该节点是否存在于集合中如果存在则说明链表中存在环如不存在继续遍历如果遍历结束后仍未发现当前遍历节点存在于集合中则链表中不存在环。
上面提到的方式简单直接但是在面试中一般不允许使用has或者集合的方式。除此之外我们可以考虑双指针如果链表中存在环则快慢指针一定会相遇我们假设fast指针每次走两步slow指针每次走一步当fast指针即将追上slow指针时存在两种情况fast指针与slow指针相差两步或者相差一步当相差一步时下一次fast指针走两步slow指针走一步相遇当相差两步时下一次slow指针走一步,fast指针走两步,变成相差一步的情况综上只要链表中存在环slow指针和fast指针一定会相遇。
代码实现
使用集合实现
public boolean hasCycle(ListNode head) {ListNode current head;SetListNode set new HashSet();while(current!null){if(set.contains(current)){return true;}else{set.add(current);}current current.next;}return false;
}使用双指针实现
public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while(fast!nullfast.next!null){fast fast.next.next;slow slow.next;if(fastslow){return true;}}return false;
}环形链表 II
问题描述
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改 链表。详见leetcode142
问题分析
找环的入口比较复杂可以结合下图进行理解。假设链表中存在环非环长度为a,环长度为b,则使用快慢指针一定会相遇。我们分析相遇时的情况。fast指针式slow指针速度的两倍则f2s,fast比slow指针多走了n个环的长度fsnb,联立方程得f2nb,snb,当s走到环的入口时,s anb我们想要找到环的入口,只需要让slow指针在走a步如何确定a的值呢我们仍然使用双指针来实现。让fast指针指向head每次走一步slow与fast同步走两者在一起走a步在环入口相遇 代码实现
public ListNode detectCycle(ListNode head) {ListNode slow head;ListNode fast head;while(fast!nullfast.next!null){fastfast.next.next;slow slow.next;if(fastslow){break;}}if(fastnull||fast.nextnull){return null;}fast head;while(fast!slow){fast fast.next;slow slow.next;}return slow;
}总结
链表没有下标所以只能靠指针遍历的方式操作元素但是一个指针在链表有环的前提下无法确定终止条件所以我们使用双指针来解决链表环的问题常见环的问题就是判断是否有环和找到环的入口上面的思路可能比较复杂可以结合图示来理解。
