如何检查一个单向链表上是否有环

1, 最简单的方法, 用一个指针遍历链表, 每遇到一个节点就把他的内存地址(java中可以用object.hashcode())做为key放在一个HashMap中. 这样当HashMap中出现重复key的时候说明此链表上有环. 这个方法的时间复杂度为O(n), 空间同样为O(n)。

2, 使用反转指针的方法, 每过一个节点就把该节点的指针反向，如果单链表存在环，那么遍历指针会回到头节点，可以通过判断遍历指针来判断。这个算法的时间复杂度是O(n)，空间为O(1)。但是缺点是会破坏原来的链表结构。

3、使用快慢指针追逐，快指针每次遍历前进2步，慢指针每次前进1步，如果单链表存在环，那么快指针肯定能追上慢指针，可以直接判断指针是否相同即可。这个算法的时间复杂度是O(n)，空间为O(1)。这个算是最优秀的判定方法。

 

示例代码如下：

 

package com.xx.dataStructure.linklist;

import java.util.HashMap;
import java.util.Map;


//节点定义
class Node {
	public int data;
	public Node next;
	
	Node (int data,Node next){
		this.data = data;
		this.next = next;
	}
	
	@Override
	public int hashCode(){
		return data ;
	}
	
	@Override
	public boolean equals(Object o){
		if (o == null) 
			return false;
		if (this == o)
			return true;
		if (o instanceof Node){
			Node node = (Node)o;
			return this.data == node.data;
		}
		return false;
	}
}

//使用策略模式
interface IsCycle {
	boolean isCycle(Node h);
}

abstract class AbstractCycle implements IsCycle{
	protected String name ;
	
	public String getName(){
		return name;
	}
}

//hash计数法
class HashCalculate extends AbstractCycle {
	{
		name = " HashCalculate algorithm ";
	}
	
	@Override
	public boolean isCycle(Node h) {
		if (h == null || h.next == null) 
			return false;
		boolean result = false;
		Node p = h.next;
		if (p.next == null) 
			return true;
		if (p.next == p) 
			return true;
		
		//循环计数
		Map<Integer, Node> map = new HashMap<Integer,Node>(0);
		while(p != null){
			Integer hashCode = p.hashCode();
			if (!map.containsKey(hashCode)){
				map.put(hashCode, p);
			}else {
				result = true;
				break;
			}
			p = p.next;
		}
		
		return result;
	}
}

//逆序链表法
class ReverseLinkedList extends AbstractCycle {
	
	{
		name = " Reverse algorithm ";
	}
	
	@Override
	public boolean isCycle(Node h) {
		if (h == null || h.next == null) 
			return false;
		boolean result = false;
		Node p = h.next;
		Node startNode = p;
		h.next = null;
		if (p.next == p) 
			return true;
		if (p.next == null)
			return false;
		int i = 0;
		while(p != null ){
			Node cNode = h.next;
			h.next = p;
			p = p.next;
			h.next.next = cNode;
			i++;
			if (h.next == startNode && i > 1){
				result = true;
				break;
			}
		}
		return result;
	}
}

//快慢指针追逐判定法
class PointChase extends AbstractCycle {
	
	{
		name = " PointChase algorithm ";
	}
	
	@Override
	public boolean isCycle(Node h) {
		if (h == null || h.next == null) 
			return false;
		boolean result = false;
		Node p = h.next;
		if (p.next == null)
			return false;
		if (p.next == p) 
			return true;
		Node slow = p, fast = p.next;
		
		while( slow  != null && fast.next != null){
			if (slow == fast){
				result = true;
				break;
			}else {
				slow = slow.next;
				fast = fast.next.next;
			}
		}
		return result;
	}
}

public class LinkedList {
	
	static Node h1 = null;
	
	static Node h2 = new Node(-1,null);
	
	static Node h3 = new Node(-1,new Node(0,new Node(1,null)));
	
	static Node h4 = null;
	
	static Node tailNode = null;
	
	static Node cycleBeginNode = null;
	
	static {
		tailNode = new Node(99,null);
		cycleBeginNode = new Node(8,new Node(9,tailNode));
		tailNode.next = cycleBeginNode;
		h4 = new Node(-1,new Node(0,new Node(1,new Node(2,cycleBeginNode))));
	}
	
	static Node h5 = new Node(-1,new Node(0,new Node(1,new Node(2,cycleBeginNode))));
	 
	
	public static void main(String [] args){
		AbstractCycle[] methods = {
				new HashCalculate(),
				new PointChase(),
				new ReverseLinkedList()
		};
		
		for(AbstractCycle method : methods){
			System.out.println(method.getName() + "："+  method.isCycle(h1)); //false
			System.out.println(method.getName() + "："+  method.isCycle(h2)); //false
			System.out.println(method.getName() + "："+  method.isCycle(h3)); //false
			System.out.println(method.getName() + "："+  method.isCycle(h4)); //true
		}
	}
}

 扩展问题：

 

1、如果单链表有环，如何找到相交节点?

     这个问题使用快慢指针算法也非常容易，假设程序循环了N次，那么慢指针走的路程为N，快指针走的路程为2N， 由于快慢指针第一次相交，那么快指针走的路程比慢指针多环的周长，因此环的周长是N，可以在循环内部加一个计数器即可。第二步定义2个指针A,B，A从表头开始遍历，B从表头第(N)个节点开始遍历，遍历的步长均为1，那么A、B第一次相遇时的节点即为单链表的相交节点。假定相交节点到头结点的距离为X，A，B第一次在相交节点相遇的条件是A遍历的步长是X，而B距离头结点的距离是X+N，AB相遇。

2、如何解环？

    A、B指针相交后，A指针继续遍历(N-1)次，到达链表尾节点，直接把尾节点的next指针置空即可。

上一篇日志中的判断单链表是否相交的算法中，就需要先判断单链表是否有环，并解环之后才能使算法正确运行。