剑指offer JZ52 两个链表的第一个公共结点
创始人
2024-06-02 05:53:50
0

Java JZ52 两个链表的第一个公共结点


文章目录

  • Java JZ52 两个链表的第一个公共结点
  • 一、描述
  • 二、Set 解法
  • 三、差值法
  • 四、等值法


  使用Set 解法、差值法和等值法解决剑指offer 第JZ52题 两个链表的第一个公共结点的问题。


一、描述

  输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)

  例如,输入{1,2,3},{4,5},{6,7}时,两个无环的单向链表的结构如下图所示:
在这里插入图片描述
  可以看到它们的第一个公共结点的结点值为6,所以返回结点值为6的结点。
  输入描述:
  输入分为是3段,第一段是第一个链表的非公共部分,第二段是第二个链表的非公共部分,第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表,并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面,用户得到的输入只有pHead1和pHead2。
  返回值描述:
  返回传入的pHead1和pHead2的第一个公共结点,后台会打印以该节点为头节点的链表
  示例:

输入:
{1,2,3},{4,5},{6,7}
返回值:
{6,7}

二、Set 解法

  做这题最容易想到的一种解决方式就是先把第一个链表的节点全部存放到集合set中,然后遍历第二个链表的每一个节点,判断在集合set中是否存在,如果存在就直接返回这个存在的结点。如果遍历完了,在集合set中还没找到,说明他们没有相交,直接返回null即可,原理比较简单,直接看下代码

import java.util.HashSet;
/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {//判断pHead1 或者pHead2 是不是有一个为null,如果有就说明一定没有公共部分if (pHead1 == null || pHead2 == null) {return null;}//创建集合hashsetHashSet hashset = new HashSet();//复制pHead1和pHead2ListNode pNode1 = pHead1, pNode2 = pHead2;//将pNode1节点值依次放入集合hashsetwhile (pNode1 != null) {hashset.add(pNode1);pNode1 = pNode1.next;}
//遍历pNode2的节点值,看是否集合hashset 中有相同元素while (pNode2 != null) {if (hashset.contains(pNode2)) {return pNode2;}pNode2 = pNode2.next;}
//如果集合hashset不包含pNode2的任何一个结点,说明他们没有交点,直接返回nullreturn null;}
}

三、差值法

  由于两条链表在相交节点后面的部分完全相同,因此我们可以先对两条链表进行遍历,分别得到两条链表的长度,并计算差值 d。

  让长度较长的链表先走 d 步,然后两条链表同时走,第一个相同的节点即是节点。

import java.util.*;
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {int c1 = 0, c2 = 0;ListNode ta = pHead1, tb = pHead2;//先得到两个链表的长度c1和c2while (ta != null && c1++ >= 0) ta = ta.next;while (tb != null && c2++ >= 0) tb = tb.next;//判断差值int d = c1 - c2;if (d > 0) {// 说明pHead1链表长,pHead1先走 d 步while (d-- > 0) pHead1 = pHead1.next;} else if (d < 0) {// 说明pHead2链表长,pHead2先走 d 步d = -d; //将负数转为整数while (d-- > 0) pHead2 = pHead2.next;}// 判断两个链表剩余的节点值是否相同while (pHead1 != pHead2) {pHead1 = pHead1.next;pHead2 = pHead2.next;}// 相同就返回剩余链表return pHead1;}
}

四、等值法

  这是解答区的答案,是我自己想不到的,题感还是不行,只能想到普通解法,一起观摩一下这个解法吧。
  使用两个指针N1,N2,一个从链表1的头节点开始遍历,我们记为N1,一个从链表2的头节点开始遍历,我们记为N2。

  让N1和N2一起遍历,当N1先走完链表1的尽头(为null)的时候,则从链表2的头节点继续遍历,同样,如果N2先走完了链表2的尽头,则从链表1的头节点继续遍历,也就是说,N1和N2都会遍历链表1和链表2。

  因为两个指针,同样的速度,走完同样长度(链表1+链表2),不管两条链表有无相同节点,都能够到达同时到达终点。(N1最后肯定能到达链表2的终点,N2肯定能到达链表1的终点)。

  所以,如何得到公共节点:

  有公共节点的时候,N1和N2必会相遇,因为长度一样嘛,速度也一定,必会走到相同的地方的,所以当两者相等的时候,则返会第一个公共的节点
  无公共节点的时候,此时N1和N2则都会走到终点,那么他们此时都是null,所以也算是相等了。
  下面看个动态图,可以更形象的表示这个过程~

请添加图片描述

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {ListNode l1 = pHead1, l2 = pHead2;while(l1 != l2){l1 = (l1==null)?pHead2:l1.next;l2 = (l2==null)?pHead1:l2.next;}return l1;}

相关内容

热门资讯

安卓系统用的华为应用,探索智能... 你知道吗?在安卓系统里,华为的应用可是个宝库呢!它们不仅功能强大,而且使用起来超级方便。今天,就让我...
安卓变ios系统魅蓝 你知道吗?最近有个朋友突然告诉我,他要把自己的安卓手机换成iOS系统,而且还是魅蓝品牌的!这可真是让...
幻书启世录安卓系统,安卓世界中... 亲爱的读者们,你是否曾在某个夜晚,被一本神奇的书所吸引,仿佛它拥有着穿越时空的力量?今天,我要带你走...
电脑安装安卓系统进不去,安卓系... 电脑安装安卓系统后竟然进不去,这可真是让人头疼的问题啊!你是不是也遇到了这种情况,心里直呼“怎么办怎...
用键盘切换控制安卓系统,畅享安... 你有没有想过,用键盘来控制你的安卓手机?是的,你没听错,就是那个我们每天敲敲打打的小玩意儿——键盘。...
小米安卓镜像系统在哪,小米安卓... 你有没有想过,你的小米手机里有一个隐藏的宝藏——安卓镜像系统?没错,就是那个可以让你的手机瞬间变身成...
安卓手机下载排班系统,高效排班... 你有没有想过,每天忙碌的工作中,有没有什么好帮手能帮你轻松管理时间呢?今天,就让我来给你介绍一个超级...
桌面组件如何弄安卓系统,桌面组... 亲爱的桌面爱好者们,你是否曾梦想过将安卓系统搬到你的电脑桌面上?想象那些流畅的动画、丰富的应用,还有...
安卓13系统介绍视频,新功能与... 亲爱的读者们,你是否对安卓13系统充满好奇?想要一探究竟,却又苦于没有足够的时间去研究?别担心,今天...
车机安卓7.1系统,功能升级与... 你有没有发现,现在的车机系统越来越智能了?尤其是那些搭载了安卓7.1系统的车机,简直就像是个贴心的智...
安卓系统下如何读pdf,And... 你有没有遇到过这种情况:手机里存了一大堆PDF文件,可是怎么也找不到一个能顺畅阅读的工具?别急,今天...
安卓系统全国通用的吗,畅享智能... 你有没有想过,为什么你的手机里装的是安卓系统呢?安卓系统,这个名字听起来是不是有点神秘?今天,就让我...
假苹果手机8安卓系统,颠覆传统... 你有没有想过,如果苹果手机突然变成了安卓系统,会是怎样的景象呢?想象那熟悉的苹果外观,却运行着安卓的...
安卓12.0系统vivo有吗,... 你有没有听说最近安卓系统又升级啦?没错,就是那个让手机焕然一新的安卓12.0系统!那么,咱们国内的手...
核心芯片和安卓系统,探索核心芯... 你知道吗?在科技的世界里,有一对“黄金搭档”正悄悄改变着我们的生活。他们就是——核心芯片和安卓系统。...
如何调安卓系统屏幕颜色,安卓系... 亲爱的手机控们,你是否曾觉得安卓系统的屏幕颜色不够个性,或者是因为长时间盯着屏幕而感到眼睛疲劳?别担...
旧台式电脑安装安卓系统,轻松安... 你那台旧台式电脑是不是已经服役多年,性能逐渐力不从心,却又不忍心让它退役呢?别急,今天就来教你怎么给...
美国要求关闭安卓系统,科技霸权... 美国要求关闭安卓系统:一场技术革新还是政治博弈?在数字化时代,智能手机已经成为我们生活中不可或缺的一...
安卓系统日记本 你有没有发现,手机里的安卓系统日记本,简直就是记录生活点滴的宝藏库呢?想象每天忙碌的生活中,有没有那...
安卓手机广告最少的系统,探索安... 你有没有发现,用安卓手机的时候,广告总是无处不在,让人烦得要命?不过别急,今天我要给你揭秘一个秘密—...