文档章节

链表相交

九州暮云
 九州暮云
发布于 2017/11/09 16:02
字数 520
阅读 24
收藏 0

目标

找到两个链表相交的起始节点,交点表示一个链表的结尾与另一个链表中的某个节点链接,形成Y形。如图所示:

输入图片说明

具体实现

  1. 计算出两个链表的长度:a_len和b_len
  2. 再计算出两个链表长度的差:len­Diff = (a_len ~ b_len)
  3. 通过lenDiff遍历较长的链表
  4. 同时遍历这两个链表,判断是否有相同的节点node,如果有这个节点就返回,没有就返回null

时间复杂度O(n),空间复杂度O(1)。

实现代码:

public class FindIntersectionOfLinkedLists {

	public LinkedListIntersection a;
	public LinkedListIntersection b;
	public void createLists(){
		a = new LinkedListIntersection();
			a.addAtEnd(1);
			a.addAtEnd(10);
			a.addAtEnd(20);
			Node tmp = a.addAtEnd(30);
			a.addAtEnd(40);
			a.addAtEnd(50);
			a.addAtEnd(60);
			System.out.print("List A : ");
			a.display();
		b = new LinkedListIntersection();
			b.addAtEnd(5);
			b.addAtEnd(15);
			b.createIntersection(a,tmp);
			System.out.print("List B : ");
			b.display();
	}
	public void findIntersectionByLength(){
		int a_len=0;
		int b_len=0;
		int lenDiff=0;
		boolean intsctFound = false;
		Node an = a.head;
		Node bn = b.head;
		//计算两个链表的长度:a_len和b_len
		while(an!=null){
			an=an.next;
			a_len++;
		}
		while(bn!=null){
			bn=bn.next;
			b_len++;
		}
		
		// 计算a、b两个链表的长度之差,用长链表减去短链表,根据差值遍历最长的链表,移动最长链表的节点指针,最终的结果会使两个链表长度相等
		an = a.head;
		bn = b.head;
		if(a_len>b_len){
			lenDiff = a_len-b_len;
		//	System.out.print("length diff " +lenDiff );
			while(lenDiff!=0){
				an = an.next;
				lenDiff--;
			}
		}else{
				lenDiff = b_len-a_len;
			while(lenDiff!=0){
				bn = bn.next;
				lenDiff--;
			}
		}
		
		// 同时遍历两个链表,找出交点
		while(an!=null && bn!=null){
			//System.out.print(an.data + " " + bn.data);
			if(an==bn) {
				System.out.print("交点是 " + an.data);
				intsctFound = true;
				break;
			}
			else{
				an = an.next;	
				bn = bn.next;
			}
		}
		if(!intsctFound){
			System.out.print("没有找到交点");
		}
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		FindIntersectionOfLinkedLists i = new FindIntersectionOfLinkedLists();
		i.createLists();
		i.findIntersectionByLength();
	}
}
class Node{
	public int data;
	public Node next;
	public Node(int data){
		this.data = data;
		this.next = null;
	}
}
class LinkedListIntersection{
	public Node head;
	public LinkedListIntersection(){
		head=null;
	}
	
	public Node addAtEnd(int data){
		Node n = new Node(data);
		
		if (head==null){
			n.next = head;
			head = n;
		}
		else{
			Node currNode = head;
			while(currNode.next!=null){
				//System.out.print("---->" + currNode.data);
				currNode = currNode.next;
			}
			currNode.next = n;
		}
		return n;
	}
	public void createIntersection(LinkedListIntersection a, Node nd){
		Node hd = a.head; 
		while(hd!=nd){
			hd = hd.next;
		}
		Node currNode = head;
			while(currNode.next!=null){
				currNode = currNode.next;
			}
			currNode.next = hd; ;
	}
	public void display(){
		System.out.println("");
		Node currNode = head;
		while(currNode!=null){
			System.out.print("->" + currNode.data);
			currNode=currNode.next;
		}
		System.out.println("");
	}
}

编译自:Find Intersection Point in Two Linked List

© 著作权归作者所有

上一篇: 链表反转
九州暮云
粉丝 71
博文 160
码字总数 116799
作品 0
海淀
高级程序员
私信 提问
判断两个链表是否交叉,并求出交叉点

在前面一篇文章中讲了如何判断一个链表中有环,如果有环的话,又如何判断出环出现在哪里 http://blog.csdn.net/xie376450483/archive/2010/08/19/5825261.aspx 今天要讲的和那篇类似,就是给...

晨曦之光
2012/04/13
3.1K
0
链表面试题(下)

一、题目 1、判断单链表是否带环?若带环,求环的长度?求环的入口点? ①链表是否带环问题。( 定义两个指针同时指向头节点,一个快指针,一个慢指针,两个指针同时遍历链表,快指针一次走两...

qq_38646470
2018/01/08
0
0
单链表有环判断,环节点、俩链表相交

【摘要】有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。 1、如何判断一个链表是不 是这类链表? 2、如果链表为存在环,如...

eric_zhang
2012/06/20
337
0
面试精选之链表问题集锦

链表问题是面试过程中经常被问到的一部分,很考查编程功底。最近刷了 LeetCode 上链表部分的面试题,我总结了一些有代表性的链表问题。 本文使用的是 Java 语言,下面是所用到的链表节点的定...

JohnnyShieh
2017/11/27
0
0
判断两个链表是否相交,若相交,则找出相交的第一个节点

节点的定义: 判断两个链表是否相交: 思路: 如果两个链表相交,则它们的尾节点一定相同,所以遍历每个链表,找到它们的尾节点,进行判断即可. 引申:如果两个链表相交,如何找到它们相交的...

tsmyk0715
2016/08/08
12
0

没有更多内容

加载失败,请刷新页面

加载更多

【0911】linux软件包安装和卸载

【0911】linux软件包安装和卸载 一、安装软件包的三种方法 1、rpm工具:与win中的exe安装包类似,红帽子公司包管理系统 2、yum工具:属于一种用python开发的工具,支持自动的安装依赖的包 3、...

飞翔的竹蜻蜓
26分钟前
3
0
【外行学IT】手机网页自适应之rem和viewport

在写手机网页时,对于像素的问题会非常困惑,初学者很多时候会因为那么一个小点的问题解决不了,或者无法理解透彻就放弃了学习。 我在学习写手机网页时也困惑了许久,出现过下面的问题: 图片...

前端老手
37分钟前
5
0
三、Java设计模式之单一职责原则

定义:不要存在多于一个导致类变更的原因。 一个类、接口、方法只负责一项职责 优点:降低类的复杂度、提高类的可读性,提高系统的可维护性、降低变更引起的风险

东风破2019
45分钟前
4
0
搭建高可用MongoDB集群(分片)

搭建高可用MongoDB集群(分片) KaliArch关注1人评论28269人阅读2017-12-04 21:57:41 MongoDB基础请参考:https://blog.51cto.com/kaliarch/2044423 MongoDB(replica set)请参考:https:/...

linjin200
今天
6
0
Pandas DataFrame创建方法大全

Pandas是Python的数据分析利器,DataFrame是Pandas进行数据分析的基本结构,可以把DataFrame视为一个二维数据表,每一行都表示一个数据记录。本文将介绍创建Pandas DataFrame的6种方法。 创建...

汇智网教程
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部