检测链表中是否有环

Apr 26

luoxi坨坨胡同儿 , No Comments

其实这是个经典算法题，但我却刚刚听说，可见对于算法，我已经漠视很久了。这不是一个专业程序员应该有的状态…… 在此推荐一篇关于程序员能力矩阵的文章，please enjoy~ :)

这个题目是听公司同事说起的，当时我的第一反应也是建立一个哈希表，然后循环检查元素是否已经存在于这个表中，没有就添加进去，并检查下一个，如果有就说明此链表是个环。甚至为了优化性能，可以隔几个检查一次，这样还能减少比对次数。后来google了一下，豁然开朗~

简单说来，就是设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步(如果能证明其他数值性能更高，欢迎补充)，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)，具体到Java代码是这样的：

首先先定义LinkedNode类，为了简化代码，我只给它设置了一个属性：next

public class LinkedNode {
 
	private LinkedNode next = null;
 
	public void setNext(LinkedNode _next) {
		this.next = _next;
	}
 
	public LinkedNode next() {
		return this.next;
	}
}

然后开始写测试代码：

public class CircleChecker {
 
	public static final int HASHCHECK = 1;
	public static final int STEPCHECK = 2;
 
	/**
	 * Generate a linked list
	 * @param circle if true, return a circle list
	 * @param capacity list size
	 * @return linked list
	 */
	private List<LinkedNode> getLinkedList(boolean circle, int capacity) {
		List<LinkedNode> list = new LinkedList<LinkedNode>();
		LinkedNode head = new LinkedNode();
		list.add(head);
		while (--capacity > 0) {
			LinkedNode node = new LinkedNode();
			list.get(list.size() - 1).setNext(node);
			list.add(node);
		}
		if (circle) {
			list.get(list.size() - 1).setNext(head);
		}
		System.out.println("List size is :" + list.size() + "\r\n");
		return list;
	}
 
	public boolean hashCheck(List<LinkedNode> list) {
		boolean hasCircle = false;
		Set<LinkedNode> hash = new HashSet<LinkedNode>();
 
		LinkedNode node = list.get(0);
		hash.add(node);
		int times = 0;
		int step = 2;
		while (node.next() != null) {
			for (int i = 0; i < step && node.next() != null; i++) {
				node = node.next();
			}
			if(!hash.add(node)) {
				hasCircle = true;
				break;
			}
			times++;
		}
		System.out.println("Check Time: " + times);
		return hasCircle;
	}
 
	public boolean stepCheck(List<LinkedNode> list) {
		boolean hasCircle = false;
		int i;
		int step1 = 1;
		int step2 = 2;
 
		LinkedNode node1 = list.get(0);
		LinkedNode node2 = list.get(0);
		int times = 0;
		while (node1.next() != null && node2.next() != null) {
			for (i = 0; i < step1 && node1.next() != null; i++) {
				node1 = node1.next();
			}
			for (i = 0; i < step2 && node2.next() != null; i++) {
				node2 = node2.next();
			}
			if (node1 == node2) {
				hasCircle = true;
				break;
			}
			times++;
		}
		System.out.println("Check Time: " + times);
		return hasCircle;
	}
 
	public void startCheck(List<LinkedNode> list, int mode) {
		long start = System.currentTimeMillis();
		boolean result = false;
		switch (mode) {
		case HASHCHECK:
			System.out.println("[Hash Check]");
			result = this.hashCheck(list);
			break;
		case STEPCHECK:
			System.out.println("[Step Check]");
			result = this.stepCheck(list);
			break;
		default:
			System.err.println("Unsupported Mode");
		}
		long end = System.currentTimeMillis();
		System.out.println("RunningTime: " + (end - start));
		System.out.println("Result is " + result + "\r\n");
	}
 
	public static void main(String[] arg) {
		CircleChecker app = new CircleChecker();
		List<LinkedNode> testList = app.getLinkedList(true, 500000);
		app.startCheck(testList, HASHCHECK);
		app.startCheck(testList, STEPCHECK);
	}
 
}

运行结果如下：
List size is :500000

[Hash Check]
Check Time: 249999
RunningTime: 453
Result is true

[Step Check]
Check Time: 499999
RunningTime: 40
Result is true

这是对一个环路链表的检测结果，下面再试试无环路链表。把main函数中的

List<LinkedNode> testList = app.getLinkedList(true, 500000);

改为：

List<LinkedNode> testList = app.getLinkedList(false, 500000);

运行结果如下：
List size is :500000

[Hash Check]
Check Time: 250000
RunningTime: 448
Result is false

[Step Check]
Check Time: 250000
RunningTime: 24
Result is false

可见虽然哈希表检查法可能在比较次数上较少，但是总耗时多了很多，主要耗费在hash.add(node)上，因为选择的是Set，所以为了保证元素唯一性，在add数据时会检查是否已存在。而且当要检查的元素数量巨大时，要占用非常大的内存，甚至OutOfMemoryError。而快慢两步走法（sorry，我起得名字有点土），仅仅进行指针比较既可，极其快速，而且不占内存！
这才是我们应该追求的终极目标

Leave a Reply