栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

2.5 Floyd链表查环算法

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

2.5 Floyd链表查环算法

文章目录
  • 原理
  • Node代码
  • List类代码
  • 测试代码
  • 复杂度分析

原理

  链表查环是一个笔试面试热门题目,但是我完结这个专栏时没写。链表查环有几种常见的方法,一个办法是使用hash map或hash set来记录已经访问过的节点,这个方法的缺点是空间复杂度高。其余的方法,比如节点加是否已访问属性,缺点也是如此。
  著名的计算机算法科学家Floyd发明了一个算法,使用了两个指针,一个快指针和一个慢指针。快指针一次走两步,慢指针一次走一步,如果存在环,这两个指针一定会相遇。这原理很简单,就是个小学数学题,在圆形的跑道上,存在速度差一定会相遇。在环上不存在小数,所以速度差为1才会最终相遇。所以慢指针一次走两步,快指针一次走三步也是会相遇的。但是最简洁的速度1和速度2的快慢组合。

Node代码
package com.youngthing.list.linked;


public class Node {

    private Node prev;
    private Node next;
    private T key;

    public Node(T value) {
        key = value;
    }

    public Node getPrev() {
        return prev;
    }

    public void setPrev(Node prev) {
        this.prev = prev;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
        if (next != null) {
            next.prev = this;
        }
    }

    public T getKey() {
        return key;
    }

    public void setKey(T key) {
        this.key = key;
    }
}

List类代码
package com.youngthing.list.linked;


public class LinkedList {

    private Node head;
    private Node tail;
    private int length;

    public void addLast(T value) {
        Node node = new Node<>(value);
        addLast(node);
    }

    public void addLast(Node node) {
        if (head == null) {
            tail = head = node;
        } else {
            tail.setNext(node);
            tail = node;
        }
        length++;
    }

    public T removeLast() {
        if (head == null) {
            throw new RuntimeException("链表为空");
        }
        T temp = tail.getKey();
        if (length == 1) {
            tail = head = null;
            return temp;
        } else {
            tail = tail.getPrev();
        }
        length--;
        return temp;
    }

    public void addFirst(T value) {
        Node node = new Node<>(value);
        if (head == null) {
            tail = head = node;
        } else {
            node.setNext(head);
            head = node;
        }
        length++;
    }

    public T removeFirst() {
        T temp = head.getKey();
        if (length == 1) {
            tail = head = null;
        } else {
            head = head.getNext();
        }
        length--;
        return temp;
    }

    public boolean floyd() {
        Node slow = head;
        Node fast = head;
        while (slow!=null && fast!= null && fast.getNext()!= null) {
            slow = slow.getNext();
            fast = fast.getNext().getNext();
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

测试代码
package com.youngthing.list.test.linked;

import com.youngthing.list.linked.LinkedList;
import com.youngthing.list.linked.Node;


public class FloydTest {

    public static void main(String[] args) {
        final LinkedList list = new LinkedList<>();
        final Node n1 = new Node<>(1);
        final Node n2 =new Node(2);
        final Node n3 =new Node(3);
        final Node n4 =new Node(4);
        final Node n5 =new Node(5);
        final Node n6 =new Node(6);
        final Node n7 =new Node(7);
        list.addLast(n1);
        list.addLast(n2);
        list.addLast(n3);
        list.addLast(n4);
        list.addLast(n5);
        list.addLast(n6);
        list.addLast(n7);
        list.addLast(n2);
        System.out.println(list.floyd());
    }

}

  测试结果为true,代表存在环。

复杂度分析

  存在环的链表,只有一个模式,就是链表加上一个环,形成一个数字6的形状。假设这个6字形,链表段长度为a,环段的长度为b。慢指针走完链表段时,到达环段和链表段的交点时,快指针已经走了 2 a 2a 2a的距离。因为速度差为1,所以根据小学的应用题公式,所以在慢指针再跑一个 b − a b-a b−a长度后相遇。假设慢指针还要跑环之前的链表段长度 a a a。这两段加起来刚好是链表的总长度n,所以总时间复杂度就是 O ( n ) O(n) O(n)。空间复杂度就是两个指针所占的空间,所以空间复杂度为 O ( 1 ) O(1) O(1)。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/947152.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号