链表环相关问题

链表环相关问题,第1张

链表环相关问题

文章目录
    • 1. 判断链表是否有环
      • 解法一 哈希表
      • 解法二(最优解) 快慢指针
    • 2. 获取环的入口节点
      • 题解参考
      • Java实现
    • 3. 计算环的长度
    • 为什么快慢指针一定会相遇?

1. 判断链表是否有环
  • 环形链表
解法一 哈希表
  • 将遍历过的节点存入哈希表,利用哈希表数据唯一性
 
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. 链表中环的入口节点
题解参考
  • 题解
Java实现
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. 计算环的长度
  • 在解决前两个问题的基础上,此问题变得很简单了
  • 参考文章
为什么快慢指针一定会相遇?
  • 快慢指针慢指针和快指针一定会相遇

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5686557.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存