几个和带环链表有关的问题

2021/04/22

前言

image.png

如下链表是一个带环链表,环的入口是 2,环的长度为 4。

image.png

链表节点定义如下:

// 单链表节点定义,参考 Leetcode
class ListNode<T> {
    public T val;
    public ListNode<T> next;

    public ListNode(){
        this(null,null);
    }

    public ListNode(T val){
        this(val,null);
    }

    public ListNode(T val, ListNode next){
        this.val = val;
        this.next = next;
    }
}
复制代码

判断链表是否有环

判断链表是否有环,比较好的方法是 快慢指针法

定义两个指针 fast, slow ,初始都指向头节点。快指针 fast 一次向后移动一位,慢指针 slow 一次向后移动两位;如果快慢指针相遇(指向同一个节点且都不为空),说明链表存在环。

// 判断链表是否有环
public boolean isLoop(){
    if(this.head == null){
        return false;
    }
    ListNode<T> fast = head;
    ListNode<T> slow = head;
    while(fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow){
            return true;
        }
    }
    return false;
}
复制代码

确定环入口

如果链表存在环,如何确定环的入口(环交汇的节点)是哪个节点?

假设链表环的入口为 entrance ,快慢指针相遇的节点为 meet,由于快指针的速度是慢指针的 2 倍,所以当快慢指针相遇时,慢指针走过的距离为 s,则快指针走过的距离为 2s

假设头节点到环入口的距离为 he,环入口到相遇节点的距离为 em,环的长度为 r

image.png

我们可以得到:

s=he+em2s=he+em+nrs = he + em \\ 2s = he + em + n*r

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享