剑指 offer代码解析——面试题37两个链表的第一个公共结点

本题的详细解析均在代码注释中:

import java.util.Stack;

/**
 * 题目:输入两个链表,找出他们的第一个公共结点
 * @author 大闲人柴毛毛
 * @date 2016年3月25日
 */
public class FirstCommonNode {
	/**
	 * 分析:本题最直观的思路就是:顺序遍历第一个链表,每遍历第一个结点的时候,再顺序遍历第二个链表,寻找相同的结点。
	 * 假设两个链表的长度分别为n和m,那么这种方法的时间复杂度为O(n*m)。
	 * 下面我们寻找更为高效的方法。
	 */
	
	/**
	 * 根据单链表的特性,我们可以得出以下结论:
	 * 两个链表具有公共结点,也就是两个链表在公共结点处发生交汇。并且公共结点以后的所有结点均重合。
	 * 
	 * 根据上述结论,我们进一步可以推断:
	 * 如果两个链表有公共结点,那么两个链表的尾结点一定相同。我们从两条链表的尾结点开始向前遍历,直到发现两个结点不一样为止。
	 * 但由于单链表无法从后向前遍历,因此我们可以用两个栈来存放两条链表的所有结点,然后分别比较栈顶的结点是否相同。
	 * 这种方式采用“空间换时间”的思想,空间复杂度为O(m+n),时间复杂度为O(m+n)
	 * 代码如下:
	 */
	
	/**
	 * 获取两条链表的第一个公共结点
	 * @param first1
	 * @param first2
	 * @return
	 */
	public static <T> Node<T> getFirstCommonNode_1(Node<T> first1,Node<T> first2){
		//若链表为空
		if(first1==null || first2==null){
			System.out.println("链表为空!");
			return null;
		}
		
		//创建两个栈,存储链表的结点
		Stack<Node<T>> stack1 = new Stack<Node<T>>();
		Stack<Node<T>> stack2 = new Stack<Node<T>>();
		
		//将第一条链表的结点存入stack1中
		Node<T> p = first1;
		while(p!=null){
			stack1.push(p);
			p = p.next;
		}
		//将第二条链表的结点存入stack2中
		p = first2;
		while(p!=null){
			stack2.push(p);
			p = p.next;
		}
		
		//比较栈顶结点是否相同
		Node<T> commonNode = null;//用于存储公共结点
		while(stack1.peek() == stack2.peek()){
			commonNode = stack1.peek();
			stack1.pop();
			stack2.pop();
		}
		
		return commonNode;
	}
	
	
	
	/**
	 * 上述方法时间复杂度有所提升,但需要额外的存储空间,是否有鱼和熊掌兼得的方法呢?
	 * 
	 * 上述方式使用了栈,因此需要额外的存储空间;而使用栈是因为需要从后向前遍历;之所以要从后向前遍历是因为两条单链表的长度不一样,而发生重合的部分是在链表的尾部。
	 * 因此,如果我们把两条长度不等的单链表中长的那部分头切掉,使得两条链表一样长,然后从前向后遍历,只要发现哪个结点相同,该结点就是我们要找的第一个公共结点。
	 * 代码如下:
	 */
	public static <T> Node<T> getFirstCommonNode_2(Node<T> first1,Node<T> first2){
		//链表为空
		if(first1==null || first2==null){
			System.out.println("链表为空!");
			return null;
		}
		
		//遍历单链表1,统计其长度
		int len1 = 0;
		Node<T> p = first1;
		while(p!=null){
			len1++;
			p = p.next;
		}
		
		//遍历单链表1,统计其长度
		int len2 = 0;
		p = first2;
		while(p!=null){
			len2++;
			p = p.next;
		}

		//计算长度差
		int diff = len1 - len2;
		
		//若第一条链表长,则将第一条链表头上多出来的部分截掉
		if(diff > 0)
			for(int i=0;i<diff;i++)
				first1 = first1.next;
		//若第2条链表长,则将第2条链表头上多出来的部分截掉
		else
			for(int i=0;i<diff;i++)
				first2 = first2.next;
		
		//同时从前向后扫描两个链表,寻找相同的结点
		Node<T> p1 = first1;
		Node<T> p2 = first2;
		while(p1 != p2 && p1!=null && p2!=null){
			p1 = p1.next;
			p2 = p2.next;
		}
		
		return p1;
	}
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		//创建两个链表
		Node<Integer> first1 = new Node<Integer>();
		Node<Integer> node2 = new Node<Integer>();
		Node<Integer> node3 = new Node<Integer>();
		Node<Integer> first2 = new Node<Integer>();
		Node<Integer> node4 = new Node<Integer>();
		Node<Integer> node5 = new Node<Integer>();
		
		first1.data = 111;
		node2.data = 2;
		node3.data = 3;
		node4.data = 4;
		node5.data = 5;
		first2.data = 222;
		
		//使公共结点为node3
		first1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		
		first2.next = node3;
		
		System.out.println(getFirstCommonNode_2(first1, first2).data);
	}
	
}



/**
 * 链表结点
 */
class Node<T>{
	public T data;
	public Node<T> next;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏黑泽君的专栏

java基础学习_集合类03_用户登录注册案例(集合版)、Set集合、Collection集合总结_day17总结

============================================================================= ==...

1052
来自专栏海说

16、Collection接口及其子接口Set和List(常用类LinkedList,ArrayList,Vector和Stack)

16、Collection接口 Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(...

2280
来自专栏从零开始学 Web 前端

07 - JavaSE之容器

Collection 接口的子接口分为:Set接口(包含 HashSet类) + List接口(包含LinkedList 类和 ArrayLis t类) Ma...

992
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题16反转单链表

本题的详细解析均在代码中注释: /** * 题目:将单链表反转,并输出反转后链表的头结点 * @author 大闲人柴毛毛 */ public class...

41911
来自专栏小怪聊职场

Java|Map、List与Set的区别

47912
来自专栏LinkedBear的个人空间

唠唠SE的集合-01——Collection接口

当集合中存储的对象类型不同时,那么会导致程序在运行的时候的转型异常,所以jdk1.5加入了泛型机制。

692
来自专栏Android群英传

深入Java源码解析容器类List、Set、Map

2233
来自专栏机器学习从入门到成神

Java使用增强for循环和迭代器遍历Map集合

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

3841
来自专栏浪淘沙

java学习day07 常用API

2018.6.11 1.object 所有类的父类 toString 打印对象的地址值 hashCode 对象的存储位置的算法 ...

1423
来自专栏desperate633

Top 6 常见问题关于Java中的Map1 将Map转换成一个List2 遍历map中的键值对3 根据Map的key值排序4 根据Map的value值排序5 初始化一个静态的不可变的Map6 Has

我们都知道Map是一种键-值对的数据结构,每个键都是唯一的!本文讨论了关于Java中Map使用的最常见的8个问题。为了叙述的简单,所有的例子都会使用泛型。并且本...

813

扫码关注云+社区

领取腾讯云代金券