美文网首页
小灰算法(一): 快慢指针求解链表是否有环

小灰算法(一): 快慢指针求解链表是否有环

作者: 没有故事的老大爷 | 来源:发表于2019-11-04 21:28 被阅读0次

文章参考自书籍:《漫画算法-小灰的算法之旅》-魏梦舒

单向有环链表

如图是一个有环的单向链表,那么我们如何判断一个单向链表有环吗?会被大家常想到的方法是穷举遍历或者借助一个hashSet来判断。穷举的时间复杂度是O(N*N),借助hashSet的时间复杂度是O(N),空间复杂度是O(N)。

所以我们今天来介绍一种稍微更优的算法来求解单向链表是否有环。首先我们使用两个指针p1和p2指向链表头结点。然后让p1以速度1向后移动,p2以速度2向后移动。如果两个指针会相遇,则表示此链表有环。

  1. 首先p1和p2指向头结点:


  2. p1一次移动一步到2这个节点,p2一次移动两步到5这个节点

  1. 继续移动


  2. 继续...


  3. 在3这个节点相遇,则表示此链表有环


为什么这样就能判断链表有环了呢?我们不妨试想一下,如果两个速度不同的人在操场绕圈一直跑,一段时间后速度快的人自然又追上慢的那位了。原因就是因为操场也是个环。这种算法的时间复杂度是O(N),空间复杂度是O(1)。

  1. 接下来我们用代码实现一下
/**
 * 链表节点
 * @author chenchen
 */
public class Node {

    private int value;

    private Node next;

    public Node (int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}



/**
 * 判断一个单向链表是否有环
 * @author chenchen
 */
public class Test {

    public static void main(String[] args) {
        // 1. 创建一个有环单向链表
        Node n1 = new Node(8);
        Node n2 = new Node(2);
        Node n3 = new Node(5);
        Node n4 = new Node(6);
        Node n5 = new Node(3);
        Node n6 = new Node(9);
        Node n7 = new Node(7);

        n1.setNext(n2);
        n2.setNext(n3);
        n3.setNext(n4);
        n4.setNext(n5);
        n5.setNext(n6);
        n6.setNext(n7);
        n7.setNext(n4);

        // 2. 判断是否有环
        boolean result = isLoopLink(n1);
        System.out.println(result);

    }

    /**
     * 判断此单向链表是否有环
     * @param head Node
     * @return boolean
     */
    private static boolean isLoopLink(Node head) {
        // 1. p1,p2指向头结点
        Node p1 = head;
        Node p2 = head;

        // 2. p1和p2以不同的速度向后移动
        while (null != p1 && null != p2.getNext()) {
            p1 = p1.getNext();
            p2 = p2.getNext().getNext();
            if (p1 == p2) {
                return true;
            }
        }
        return false;
    }

}

单向有环链表

很明显,咱这个环的长度是4,入环的节点是6. 所以有了下面两个扩展问题大家来思考一下。

  1. 扩展一:如何求出环的长度
    思路:首次相遇后,p2和p1继续移动,下次相遇时p2比p1整整多跑了一圈。所以环长=速度差*前进次数

  2. 扩展二:如何求出入环节点


如图,我们假设头结点到入环点的距离是D, 入环点到首次相遇点的距离是s1, 首次相遇点继续往后走再回到入环点的距离是s2. 那么两指针首次相遇时各走了多少距离呢。
p1:D+S1
p2: D+S1+S2+S1
因为p2速度是p1的二倍,所以有
2(D+S1) = D+S1+S2+S1
整理得到: D = S2
有了这个结论那么我们将p1重置回头结点,p2在首次相遇点。两个指针都是每次移动一步,这样再次相遇时就是入环点了。

作者 [@没有故事的老大爷][1]
[1]: https://www.chenchen.zone/

相关文章

  • 小灰算法(一): 快慢指针求解链表是否有环

    文章参考自书籍:《漫画算法-小灰的算法之旅》-魏梦舒 如图是一个有环的单向链表,那么我们如何判断一个单向链表有环吗...

  • 数据结构与算法整理

    (1)链表的技巧 快慢指针(找环,环入口,环长度) 双指针(倒数K个节点) 合并链表(递归求解) 约瑟夫环(环形链...

  • 快慢指针的应用

    什么是快慢指针:快慢指针是链表操作中的常用操作,最经典的应用是判断单链表中是否有环。 判断单链表是否存在环 两个指...

  • 其余代码题

    链表是否有环-done 表达式计算-done 括号匹配-done 最长有效括号长度 链表是否有环 提示:快慢指针 ...

  • 链表 - 检测环 & 环入口点

    对于链表检测是否有环,大家都知道 使用快慢指针就可以了。只要快慢指针可以相遇,那么链表一定是有环的。 一般我们都是...

  • 算法学习--双指针

    双指针分类 快慢指针 左右指针 快慢指针:主要解决链表相关问题,比如:典型的判断链表中是否包含环、链表倒是第K个节...

  • 链表环操作(java实现)

    判断链表有没有环有环链表一般我们采取快慢指针来判断链表是否有环。思路主要是:定义两个指针。fast和slow;fa...

  • 算法题整整理

    1.链表是否有环,找出环的入口 答: 是否有环,快慢指针,最后两个指针重合了,就有环。 环入口:思路如下,设hea...

  • 链表有环问题

    问题1: 给定一个链表,判断这个链表是否有环 原理:使用快慢指针法,如果链表有环,则必定存在两个指针相等. 问题2...

  • 判断单链表环的快慢指针法

    快慢指针法 算法步骤 初始化快慢指针 循环处理,快指针走两步,慢指针走一步,直到发现环或者到达链表结尾 伪代码 环...

网友评论

      本文标题:小灰算法(一): 快慢指针求解链表是否有环

      本文链接:https://www.haomeiwen.com/subject/kemrbctx.html