判断链表是否相交的几种算法

     这个是《编程之美》里面的一个题目，给出两个单项链表的头指针，h1、h2判断这2个链表是否相交？

   【解法一】直观的想法

    循环遍历h1的每一个节点，判断是否存在一个节点在h2中，由于链表无法随机访问，每次查找需要对链表h2遍历最多length(h1)次，因此算法的时间复杂度是O(length(h1)*length(h2))，显然这个方法很耗时间。

    【解法二】利用hash计数

     ①循环遍历h1，计算每个节点的hash值并存入map中；②循环遍历h2，顺序计算每个节点的hash值v，并用map.get(v)，若返回非空，则算法结束。

     第①步算法时间复杂度O(length(h1))，第②步算法时间复杂度O(length(h2))，因此hash计数 算法时间复杂度为O(max(length(h1),length(h2)))，复杂度降低到线性。但是由于使用了额外的map结构，空间复杂度为O(length(h1))。

     【解法三】链表连接

       我们分析两个单链表相交时，节点的逻辑结构如下：

    h1->P1->P2->...->Pi->...->K1->...->Km

    h2->Q1->Q2->...->Qi->...->K1->...->Km

    可以看到如果把h1链表的尾节点的next指针指向h2链表的第一个节点，那么可以看到如果h1和h2相交，则

h2变成了一个循环单链表，因此只需判断h2是否为循环链表即可。需要遍历h1和h2，因此算法时间负责度O(max(length(h1),length(h2)))，空间负责度为O(1)。但是这个算法的缺点是需要链接h1和h2，改变链表的逻辑结构，在多线程环境下需要上锁，影响一定的性能。

     【解法四】更简单的做法，直接判断链表末节点是否相同

 

    同解法三的节点分析，如果h1和h2相交于节点K1，那么根据单链表的定义(任何节点有且仅有唯一的后继和唯一的前驱，null也算作前驱和后继吧)，因此如果h1和h2相交，那么两个链表从K1以后的后继的节点是相同的。因此判断链表是否相交，只用判断尾节点是否相同即可，只需遍历2个链表，时间复杂度为O(max(length(h1),length(h2)))，空间复杂度为O(1)。这个算法很简单优雅，赞一个。

      发散思维：

      1、如何求解两个相交链表的第一个相交节点？

      这个其实也很简单，使用小学数学知识即可解决。

      记 L1 = length(h1); L2 = length(h2);  h1和h2 由于相交，共有K个节点相同，那么两个链表的长度之差为相交节点之前的节点之差。因此我们让长链表先遍历abs(L1-L2)步，然后让两个链表同时遍历，同时判断2个链表的节点是否相同，若存在相同节点，则返回该节点，算法结束。

      2、如果两个链表中本身存在环，该如何解决？

      存在环的单链表，类似于这种形式。

    

      如果链表存在环，则上面的算法都无法返回正确结果，陷入死循环，因此首先要把环解开。下一篇日志将介绍几种检测链表是否存在环的算法。

       

package com.xx.dataStructure;

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

//节点定义
class Node {
	int data;
	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 Intersect {
	boolean isIntersect(Node h1,Node h2);
}

abstract class AbstractIntersect implements Intersect{
	protected String name ;
	
	public String getName(){
		return name;
	}
}
//循环遍历法
class FullTraverse extends AbstractIntersect{
	{
		name = " FullTraverse algorithm ";
	}
	
	@Override
	public boolean isIntersect(Node h1, Node h2) {
		if (h1 == null || h2 == null) 
			return false;
		Node i = h1.next;
		Node j = h2.next;
		for(;i != null ; i = i.next ){
			for(j = h2.next; j != null ; j = j.next){
				if (j == i)
					return true;
			}
		}
		return false;
	}
}

//hash计数法
class HashCalculate extends AbstractIntersect {
	{
		name = " HashCalculate algorithm ";
	}
	
	@Override
	public boolean isIntersect(Node h1, Node h2) {
		if (h1 == null || h2 == null) 
			return false;
		//init map
		Map<Integer,Node> map = new HashMap<Integer,Node>(0);
		Node i = h1.next;
		while(i != null){
			map.put(i.hashCode(), i);
			i = i.next;
		}
		//find the same node 
		Node j = h2.next;
		while(j != null){
			if (map.get(j.hashCode()) != null) 
				return true;
			j= j.next;
		}
		return false;
	}
}

//首尾相连法
class LinkHeadAndTail extends AbstractIntersect {
	
	{
		name = " LinkHeadAndTail algorithm ";
	}
	
	@Override
	public boolean isIntersect(Node h1, Node h2) {
		if (h1 == null || h2 == null) 
			return false;
		boolean result = false;
		Node i = h1.next;
		Node j = h2.next;
		while(i != null && i.next != null){
			i = i.next;
		}
		i.next = j;
		boolean begin = true;
		//判断h2是否为循环链表
		while(j != null ){
			if (j == h2.next && !begin ){
				result = true;
				break;
			}
			else {
				j = j.next;
				begin = false;
			}
		}
		//链表解除锁定
		i.next = null;
		return result;
	}
}

//尾节点判定法
class TailEqual extends AbstractIntersect {
	
	{
		name = " TailEqual algorithm ";
	}
	
	@Override
	public boolean isIntersect(Node h1, Node h2) {
		if (h1 == null || h2 == null) 
			return false;
		Node tail1 = h1.next;
		Node tail2 = h2.next;
		while(tail1 != null && tail1.next != null){
			tail1 = tail1.next;
		}
		while(tail2 != null && tail2.next != null){
			tail2 = tail2.next;
		}
		if (tail1 == tail2 )
			return true;
		return false;
	}
}

public class LinkedList {
	//相交节点
	static Node intersectNode = new Node(8,new Node(9,new Node(10,null)));
	//h1链表  0->1->2->8->9->10
	static Node h1 = new Node(-1,new Node(0,new Node(1,new Node(2,intersectNode))));
	//h2链表 0->11->12->13->14->8->9->10
	static Node h2 = new Node(-1,new Node(10,new Node(11,new Node(12,new Node(13,new Node(14,intersectNode))))));
	
	static Node h3 = new Node(-1,new Node(0,new Node(1,null)));
	static Node h4 = new Node(-1,new Node(10,null));
	
	static Node h5 = null;
	static Node h6 = null;
	
	static Node h7 = new Node(-1,new Node(0,null));
	static Node h8 = new Node(-1,null);
	
	public static void main(String [] args){
		AbstractIntersect[] methods = {
				new FullTraverse(),
				new HashCalculate(),
				new LinkHeadAndTail(),
				new TailEqual()
		};
		
		for(AbstractIntersect method : methods){
			System.out.println(method.getName() + "："+  method.isIntersect(h1, h2));
			System.out.println(method.getName() + "："+  method.isIntersect(h3, h4));
			System.out.println(method.getName() + "："+  method.isIntersect(h5, h6));
			System.out.println(method.getName() + "："+  method.isIntersect(h7, h8));
		}
		
	}
}

 

 

     参考书籍：《编程之美》