有环链表查找环 博客分类： java数据结构&算法 java数据结构算法环状链表linkedlist

有环链表如何高效的判断是否有环，以及在何处产生环？

采用2个指针不同步数（步数小的每次1步，步数大的每次2步），步数大的如果能够与步数小的相遇则必然存在环。

 

相遇后的情况如图，假设相遇后步数大的回绕环遍历了n遍，步数小的肯定一遍也没遍历完，假设第一段距离为a，第2段距离为c，第3段距离为b

则有（a+c）*2 = a+n（b+c）+c，转换后得 a = n（b+c） - c，也就是说，从出发点出发，移动a的距离，刚好等于相遇点出发移动n个整圈减c的距离，这个点刚好就是环产生的点，由此可以设置2个指针，分别从根节点与相遇点出发，第一次相遇的地方则是环产生的点。

完成证明后，代码较为简单，如下

 

package com.xhb.algorithms;

public class MyLinkedList {
	private LinkListNode<Integer> root = new LinkListNode<Integer>(null, null);
	private int length;
	private int point;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MyLinkedList list = new MyLinkedList(10045, 232);
		System.out.println(list.isHasRound());
		System.out.println("the point cut obj is " + list.getCutPoint());
	}

	/**
	 * 初始化一个环链表
	 */
	private MyLinkedList(int length, int point) {
		this.length = length;
		this.point = point;
		LinkListNode<Integer> current = this.root;
		for (int i = 1; i <= this.length - 1; i++) {
			current = current.next(new LinkListNode<Integer>(new Integer(i),
					null));
		}
		if (this.point < 0) {
			current.next(null);
		} else {
			LinkListNode<Integer> pointObj = this.root;
			for (int i = 0; i < point; i++) {
				pointObj = pointObj.next();
			}
			current.next(pointObj);
		}
	}

	public Integer getCutPoint() {
		LinkListNode<Integer> seekPoint = this.getSeekPoint();
		System.out.println(seekPoint.data());
		LinkListNode<Integer> a = this.root;
		while (true) {
			a = a.next();
			seekPoint = seekPoint.next();
			if (a == seekPoint) {
				return a.data();
			}
			// System.out.println(a.data() +"," + seekPoint.data());
		}
	}

	private LinkListNode<Integer> getSeekPoint() {
		LinkListNode<Integer> a = this.root;
		LinkListNode<Integer> b = this.root;
		a = a.next();
		b = b.next().next();
		while (true) {
			a = a.next();
			b = b.next();
			if (b == null) {
				return null;
			}
			if (a == b && b != null) {
				return b;
			}
			b = b.next();
			if (b == null) {
				return null;
			}
			if (a == b && b != null) {
				return b;
			}
		}
	}

	public boolean isHasRound() {
		return this.getSeekPoint() != null;
	}
}

class LinkListNode<T> {
	private LinkListNode<T> next = null;
	private T data;

	public LinkListNode(T data, LinkListNode<T> next) {
		this.data = data;
		this.next = next;
	}

	public LinkListNode<T> next() {
		return next;
	}

	public LinkListNode<T> next(LinkListNode<T> next) {
		this.next = next;
		return next;
	}

	public T data() {
		return this.data;
	}

	@Override
	public String toString() {
		return data.toString();
	}
}