- 1. 判断链表是否有环
- 解法一 哈希表
- 解法二(最优解) 快慢指针
- 2. 获取环的入口节点
- 题解参考
- Java实现
- 3. 计算环的长度
- 为什么快慢指针一定会相遇?
- 环形链表
- 将遍历过的节点存入哈希表,利用哈希表数据唯一性
public class Solution { public boolean hasCycle(ListNode head) { if(head == null) return false; Set解法二(最优解) 快慢指针s = new HashSet<>(); while(head != null){ if(!s.add(head)) return true; head = head.next; } return false; } }
- 此解法空间复杂度O(1), 时间复杂度O(n)
public class Solution { public boolean hasCycle(ListNode head) { if(head == null) return false; ListNode slowPointer = head; ListNode fastPointer = head.next; while(slowPointer != fastPointer){ if(fastPointer == null || fastPointer.next == null) //这里只需判断fastPointer return false; slowPointer = slowPointer.next; fastPointer = fastPointer.next.next; } return true; } }2. 获取环的入口节点
- 剑指 Offer II 022. 链表中环的入口节点
- 题解
public class Solution { public ListNode detectCycle(ListNode head) { if(head == null || head.next == null) return null; ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if(fast == slow) {//判断出链表有环,快指针放到链表开始,然后快慢指针同速度前进 fast = head; while(slow != fast) { slow = slow.next; fast = fast.next; } return fast; } } return null; } }3. 计算环的长度
- 在解决前两个问题的基础上,此问题变得很简单了
- 参考文章
- 快慢指针慢指针和快指针一定会相遇
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)