Question

如何高效地判断两个单链表是否有交叉

Answer 1

（1）思路分析：

• 使用蛮力法：遍历第一个链表，将第一个链表中的每个节点都和第二个链表中的每个节点比较，如果出现相等的节点时，即为相交节点。时间复杂度：O(mn)

• 使用散列表：遍历第一个链表，将第一个链表中的每个节点都存入散列表中。再次遍历第二个链表，对于第二个链表中的每个节点均检查是否已经存在于散列表中，如果存在则说明该节点为交点。时间复杂度：O(m) + O(n) = O(max(m,n))

• 使用栈求解：定义两个栈分别存储两个链表。分别遍历两个链表并压入到对应的栈中。比较两个栈的栈顶元素，如果二者相等则将该栈顶元素存储到临时变量中，并弹出两个栈的栈顶元素。重复上述操作一直到两个栈的栈顶元素不相等为止。最后存储的的临时变量即为交点。时间复杂度：O(m) + O(n) = O(max(m,n))

• 分别获得两个链表的长度，计算出两个链表的长度差d，较长的链表首先移动d步，然后两个链表同时向表尾移动，当出现两个节点相同时即为交点。时间复杂度：O(m) + O(n) = O(max(m,n))

（2）示例代码：

package cn.zifangsky.linkedlist.questions;

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

import org.junit.Test;

import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;

/**
 * 找出两个相交链表的交点
 * @author zifangsky
 *
 */
public class Question12 {
	
	/**
	 * 思路：使用散列表求解
	 * @时间复杂度 O(m) + O(n) = O(max(m,n))，即：O(m)或O(n)
	 * @param headNode
	 * @return
	 */
	public SinglyNode<Integer> findIntersection1(SinglyNode<Integer> headNode1,SinglyNode<Integer> headNode2){	
		Map<Integer,SinglyNode<Integer>> nodeMap = new HashMap<>();
	
		for(int i=1;headNode1!=null;i++){
			nodeMap.put(i, headNode1);
			headNode1 = headNode1.getNext();
		}

		while (headNode2 != null) {
			if(nodeMap.containsValue(headNode2)){
				return headNode2;
			}else{
				headNode2 = headNode2.getNext();
			}
		}
		return null;
	}
	
	/**
	 * 思路：1，分别获得两个链表的长度；2，计算出两个链表的长度差d；
	 * 		3，较长的链表首先移动d步，然后两个链表同时向表尾移动
	 * 		4，当出现两个节点相同时即为交点
	 * @时间复杂度 O(m) + O(n) + O(1) + O(d) + O(min(m,n)) = O(max(m,n))
	 * @param headNode1
	 * @param headNode2
	 * @return
	 */
	public SinglyNode<Integer> findIntersection2(SinglyNode<Integer> headNode1,SinglyNode<Integer> headNode2){
		int length1 = 0,length2 = 0; //两个链表节点数
		int diff = 0;
		SinglyNode<Integer> temp1 = headNode1,temp2 = headNode2;
		//1
		while (temp1 != null) {
			length1++;
			temp1 = temp1.getNext();
		}
		
		while (temp2 != null) {
			length2++;
			temp2 = temp2.getNext();
		}
		//2、3
		if(length1 > 0 && length2 > 0 && length2 >= length1){
			diff = length2 - length1;
			
			for(int i=1;i<=diff;i++){
				headNode2 = headNode2.getNext();
			}
		}else if(length1 > 0 && length2 > 0 && length2 < length1){
			diff = length1 - length2;
			
			for(int i=1;i<=diff;i++){
				headNode1 = headNode1.getNext();
			}
		}else{
			return null;
		}
		//4
		while(headNode1 != null && headNode2 != null){
			if(headNode1 == headNode2){
				return headNode1;
			}else{
				headNode1 = headNode1.getNext();
				headNode2 = headNode2.getNext();
			}
		}
		return null;	
	}
	
	@Test
	public void testMethods(){
		//人为构造两个相交的链表 
		SinglyNode<Integer> a = new SinglyNode<Integer>(11);
		SinglyNode<Integer> b = new SinglyNode<Integer>(22);
		
		SinglyNode<Integer> currentA = a,currentB = b;
		for(int i=3;i<=8;i++){
			SinglyNode<Integer> tmpNode = new SinglyNode<Integer>(11 * i);
			
			if(i < 7){
				if(i%2 == 0){
					currentB.setNext(tmpNode);
					currentB = tmpNode;
					
					SinglyNode<Integer> tmpNode2 = new SinglyNode<Integer>(11 * i + 1);
					currentB.setNext(tmpNode2);
					currentB = tmpNode2;
				}else{
					currentA.setNext(tmpNode);
					currentA = tmpNode;
				}
			}else{
				currentB.setNext(tmpNode);
				currentB = tmpNode;
				currentA.setNext(tmpNode);
				currentA = tmpNode;
			}

		}
		
		//遍历初始链表
		System.out.print("A: ");
		SinglyNodeOperations.print(a);
		System.out.print("B: ");
		SinglyNodeOperations.print(b);
		
		System.out.println("方法一，其交点是: " + findIntersection1(a,b));
		System.out.println("方法二，其交点是: " + findIntersection2(a,b));
	}
	
}

测试代码输出如下：

A: 11 33 55 77 88 
B: 22 44 45 66 67 77 88 
方法一，其交点是: SinglyNode [data=77]
方法二，其交点是: SinglyNode [data=77]

附：单向链表SinglyNode的定义：

package cn.zifangsky.linkedlist;

/**
 * 单链表的定义
 * 
 * @author zifangsky
 * @param <K>
 */
public class SinglyNode<K extends Object> {
	private K data; // 数据
	private SinglyNode<K> next; // 该节点的下个节点

	public SinglyNode(K data) {
		this.data = data;
	}

	public SinglyNode(K data, SinglyNode<K> next) {
		this.data = data;
		this.next = next;
	}

	public K getData() {
		return data;
	}

	public void setData(K data) {
		this.data = data;
	}

	public SinglyNode<K> getNext() {
		return next;
	}

	public void setNext(SinglyNode<K> next) {
		this.next = next;
	}

	@Override
	public String toString() {
		return "SinglyNode [data=" + data + "]";
	}

}