剑指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;}

相关内容

热门资讯

安卓子系统应用闪退,探究安卓子... 手机里的安卓子系统应用突然闪退,是不是让你心头一紧?别急,今天就来给你详细剖析一下这个让人头疼的问题...
早期使用安卓系统的手机,开启智... 你还记得那些早期使用安卓系统的手机吗?那时候,智能手机才刚刚崭露头角,安卓系统就像一颗新星,引领着手...
完全摆脱安卓系统的软件,探索无... 你有没有想过,手机里的安卓系统有时候就像是个无形的枷锁,让你觉得自由受限?别急,今天我要给你介绍一些...
苹果怎么玩安卓系统游戏,轻松实... 你有没有想过,用苹果手机也能玩安卓系统的游戏呢?是不是觉得有点不可思议?别急,今天就来给你揭秘这个神...
安卓改系统设置背景,打造专属手... 你有没有发现,你的安卓手机最近有点儿“水土不服”?运行速度慢了下来,界面也变得不那么顺眼了?别急,今...
zte电视安卓系统恢复,轻松解... 亲爱的读者,你是不是也遇到了这样的烦恼:家里的ZTE电视突然间安卓系统出了问题,屏幕上满是乱码,操作...
安卓系统相机可调尺寸,捕捉完美... 你有没有发现,现在手机的拍照功能越来越强大了?尤其是安卓系统的相机,功能丰富得让人眼花缭乱。今天,就...
联想恢复系统和安卓 你有没有想过,你的手机里那些珍贵的照片、视频和文件,如果突然不见了,你会怎么办?别担心,今天就来给你...
安卓平板刷数播系统,操作指南与... 你有没有想过,你的安卓平板电脑除了用来刷剧、玩游戏,还能干点啥?今天,就让我带你一探究竟,看看如何让...
安卓系统下密码键盘,安卓系统密... 你有没有发现,每次解锁手机时,那小小的密码键盘就像一个神秘的守护者,默默守护着你的隐私呢?今天,就让...
荣耀九零是安卓系统吗,深度解析... 你有没有听说过荣耀九零这款手机?最近它可是手机圈里的小热门呢!很多人都在问,荣耀九零是安卓系统吗?今...
安卓系统是谁的分支系统,谷歌基... 你有没有想过,安卓系统这个我们每天不离手的家伙,它究竟是从哪里来的呢?没错,它可是有一个超级厉害的“...
安卓怎么改系统壁纸,个性化你的... 手机屏幕上那单调的壁纸已经让你审美疲劳了吗?别急,今天就来教你怎么给安卓手机换上美美的系统壁纸! 一...
安卓系统动画效果图 你有没有发现,每次打开安卓手机,那些流畅的动画效果总是让人眼前一亮?今天,就让我带你一起探索安卓系统...
安卓10系统提示音,唤醒听觉感... 你有没有发现,自从你的手机升级到了安卓10系统,那提示音好像变得特别有个性呢?是不是觉得有点好奇,想...
镧系统工具箱安卓,全面解析与使... 你有没有发现,手机上的工具箱越来越强大了?今天,我要给你介绍一个特别酷的镧系统工具箱安卓版,它可是让...
姓名同步系统下载安卓,实现高效... 你有没有想过,手机里的联系人信息竟然可以如此智能地同步?今天,就让我来给你揭秘一个神奇的小工具——姓...
安卓系统声音调高,畅享极致音效... 你有没有发现,最近你的安卓手机声音好像变得特别小?是不是觉得跟以前比起来,好像少了点什么?别急,今天...
苹果系统安卓电脑版下载,轻松实... 你有没有想过,为什么苹果系统的应用总是那么吸引人?而安卓电脑版下载又有哪些独特之处呢?今天,就让我带...
安卓系统如何变得高端,五大策略... 你有没有发现,安卓系统最近好像悄悄地变了个样?不再是那个简单粗暴的小伙子,而是摇身一变,成了时尚界的...