2.6 Brent链表查环算法

2.6 Brent链表查环算法

文章目录

• 原理
• Node代码
• List代码
• 测试类代码

原理

  Brent链表查环算法，类似于Floyd算法，但是稍有不同。相同的是两者都有双指针。但是不同的是，Brent算法快指针也是一次走一步，相当于Floyd算法中的慢指针。Brent算法的慢指针，应该叫更慢的指针，且听我慢慢说。这个慢指针是停止的，在快指针走了一步、两步、四步、八步……后才移动到慢快指针的位置。所以这慢指针，移动幅度很大的，第一次移动一步，第二次移动两步，再是四步、八步，从一次移动的幅度这个角度讲，应该叫快指针，但是总在快指针后面，所以最终还是定为快指针。这有点类似与龟兔赛跑，快指针相当于乌龟，走得慢，但是踏实，一刻都不停歇，所以走在前面。而快指针相当于兔子，跑得快，但是喜欢休息。如果存在环，这两个指针一定会相遇。
  为什么会相遇呢？如果没有环，那么快指针永远走在慢指针前面，一步一步地走。如果有环，那么快指针在某个时候，就到了慢指针后面了，而满指针的停跑时长越来越大，所以一定两个指针一定会相遇。
  明白了这个，那么就很容易写代码了。

Node代码

ungthing.list.linked;/*** 2022/1/9 22:17 创建** @author 花书粉丝*/
public class Node<T> {private Node<T> prev;private Node<T> next;private T key;public Node(T value) {key = value;}public Node<T> getPrev() {return prev;}public void setPrev(Node<T> prev) {this.prev = prev;}public Node<T> getNext() {return next;}public void setNext(Node<T> next) { = next;if (next != null) {next.prev = this;}}public T getKey() {return key;}public void setKey(T key) {this.key = key;}
}

List代码

ungthing.list.linked;/*** 2022/1/9 22:17 创建** @author 花书粉丝*/
public class LinkedList<T> {private Node<T> head;private Node<T> tail;private int length;public void addLast(T value) {Node<T> node = new Node<>(value);addLast(node);}public void addLast(Node<T> 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 = Key();if (length == 1) {tail = head = null;return temp;} else {tail = Prev();}length--;return temp;}public void addFirst(T value) {Node<T> node = new Node<>(value);if (head == null) {tail = head = node;} else {node.setNext(head);head = node;}length++;}public T removeFirst() {T temp = Key();if (length == 1) {tail = head = null;} else {head = Next();}length--;return temp;}public boolean brent() {if (head == null) {return false;}Node<T> slow = head;Node<T> fast = Next();int power = 1;int length = 1;while (slow != null && fast != slow) {if (length == power) {power <<= 1;length = 0;fast = slow;}slow = Next();length++;}return slow != null;}
}

测试类代码

ungthing.list.linked.LinkedList;
ungthing.list.linked.Node;/*** Floyd测试* created at 02/06/2022** @author 花书粉丝* <a href="mailto://yujianbo@chtwm">yujianbo@chtwm</a>* @since 1.0.0*/
public class BrentTest {public static void main(String[] args) {final LinkedList<Integer> list = createCycle();System.out.println(list.brent());}private static LinkedList<Integer> createCycle() {final LinkedList<Integer> list = new LinkedList<>();final Node<Integer> n1 = new Node<>(1);final Node<Integer> n2 =new Node<Integer>(2);final Node<Integer> n3 =new Node<Integer>(3);final Node<Integer> n4 =new Node<Integer>(4);final Node<Integer> n5 =new Node<Integer>(5);final Node<Integer> n6 =new Node<Integer>(6);final Node<Integer> n7 =new Node<Integer>(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);return list;}}

  测试结果正确。