链表相交

目标

找到两个链表相交的起始节点,交点表示一个链表的结尾与另一个链表中的某个节点链接,形成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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 链表反转

    九州暮云
  • FATAL ERROR: please install the following Perl mod

    九州暮云
  • IDEA 编译运行 Spring Boot 2.0 源码

    由于Spring Boot的发布版本代码都在tag上,所以需要使用git tag命令查看所有的tag:

    九州暮云
  • Java基础-循环语句

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • Stackstorm介绍

    一、什么是stackstorm? 一句话概况:stackstorm是一个事件驱动的自动化引擎

    用户5760343
  • kafka分区数过多引发的弊端

    上篇文章我们了解到,如果一个topic分区越多,理论上整个集群所能达到的吞吐量就越大。那么,分区数越多就越好吗?显然不是。今天我们来聊下kafka在分区数过多的...

    一条老狗
  • 提升python项目完成效率的调试方法技巧(上)

    效率提升是极为重要的事情,我们的时间本来就不充裕,不应该过多将时间浪费在调试过程中。对于大型项目光有dubug是不够的,如果需要提高产品调试进度,必须需要采取一...

    OLDPAN
  • 『互联网架构』软件架构-springcloud-zuul微服务网关(下)(102)

    PS:zuul 作为网关这么重要的角色,高可用是非常有必要的。但是通常来说网关所面对的请求应该的是来于外部,所以虽然说网关可以注册到Eureka Server上...

    IT故事会
  • 操作系统核心原理-2.一些基本概念

      从概念上讲,计算机的结构是总线型的:布置一根总线将各种硬件设备挂在总线(Bus)上。

    Edison Zhou
  • VUE滚动条插件——vue-happy-scroll

    最近自己在自学vue2.0,然后就自己摸索做一个简单的后台管理系统,在做的过程中,总感觉不同浏览器自带的滚动条样式不统一,也很难看,所以就在网上找一些使用vue...

    用户1174387

扫码关注云+社区

领取腾讯云代金券