- 原理
- Node代码
- List代码
- 测试类代码
Brent链表查环算法,类似于Floyd算法,但是稍有不同。相同的是两者都有双指针。但是不同的是,Brent算法快指针也是一次走一步,相当于Floyd算法中的慢指针。Brent算法的慢指针,应该叫更慢的指针,且听我慢慢说。这个慢指针是停止的,在快指针走了一步、两步、四步、八步……后才移动到慢快指针的位置。所以这慢指针,移动幅度很大的,第一次移动一步,第二次移动两步,再是四步、八步,从一次移动的幅度这个角度讲,应该叫快指针,但是总在快指针后面,所以最终还是定为快指针。这有点类似与龟兔赛跑,快指针相当于乌龟,走得慢,但是踏实,一刻都不停歇,所以走在前面。而快指针相当于兔子,跑得快,但是喜欢休息。如果存在环,这两个指针一定会相遇。
为什么会相遇呢?如果没有环,那么快指针永远走在慢指针前面,一步一步地走。如果有环,那么快指针在某个时候,就到了慢指针后面了,而满指针的停跑时长越来越大,所以一定两个指针一定会相遇。
明白了这个,那么就很容易写代码了。
package com.youngthing.list.linked; public class NodeList代码{ 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; } }
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 brent() { if (head == null) { return false; } Node slow = head; Node fast = head.getNext(); int power = 1; int length = 1; while (slow != null && fast != slow) { if (length == power) { power <<= 1; length = 0; fast = slow; } slow = slow.getNext(); length++; } return slow != null; } }
import com.youngthing.list.linked.LinkedList;
import com.youngthing.list.linked.Node;
public class BrentTest {
public static void main(String[] args) {
final LinkedList list = createCycle();
System.out.println(list.brent());
}
private static LinkedList createCycle() {
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);
return list;
}
}
测试结果正确。



