首页 > 其他分享 >【面试题 02.07. 链表相交 简单】

【面试题 02.07. 链表相交 简单】

时间:2024-08-18 22:24:47浏览次数:13  
标签:面试题 02.07 相交 链表 headB headA 节点 指针

题目:

同:160.链表相交
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

图示两个链表在节点 c1 开始相交:
在这里插入图片描述
题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

示例 1:
在这里插入图片描述
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at ‘8’
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
为什么不是1,因为这里skipA = 2, skipB = 3,也就是跳过链表A的前2个节点,跳过链表B的前3个节点后,A链表与B链表的对应节点指针开始相等。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
示例 2:
在这里插入图片描述
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at ‘2’
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
示例 3:
在这里插入图片描述
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。


思路:

求两个链表交点节点的指针。 注意:交点不是数值相等,而是指针相等。
设「第一个公共节点」为 node ,「链表 headA」的节点数量为 a ,「链表 headB」的节点数量为 b ,「两链表的公共尾部」的节点数量为 c ,则有:

  • 头节点 headA 到 node 前,共有 a−c 个节点;
  • 头节点 headB 到 node 前,共有 b−c 个节点;

考虑构建两个节点指针 A​ , B 分别指向两链表头节点 headA , headB ,两个链表长度不一致,难点在于A和B如何同时到达两个链表中的第一个公共节点。做如下操作:

  • 指针 A 先遍历完链表 headA ,再开始遍历链表 headB ,当走到 node 时,共走步数为: a+(b−c)
  • 指针 B先遍历完链表 headB ,再开始遍历链表 headA ,当走到 node 时,共走步数为: b+(a−c)

如下式所示,此时指针 A , B 重合,并有两种情况:

a+(b−c)=b+(a−c)
  1. 若两链表 有 公共尾部 (即 c>0 ) :指针 A , B 同时指向「第一个公共节点」node 。
  2. 若两链表 无 公共尾部 (即c=0 ) :指针 A , B 同时指向 null 。

因此返回 A或B 都可。
如下图所示,为 a=5 , b=3 , c=2 示例的算法执行过程。

<iframe allowfullscreen="true" data-mediaembed="csdn" frameborder="0" id="kVC9ZTIw-1723971131424" src="https://live.csdn.net/v/embed/418316"></iframe>

面试题 02.07. 链表相交 - 力扣(LeetCode)


代码:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B) {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};

总结:

时间复杂度 O(a+b) : 最差情况下(即 ∣a−b∣=1 , c=0 ),此时需遍历 a+b 个节点。
空间复杂度 O(1) : 节点指针 A , B 使用常数大小的额外空间。

  1. 首先要理解题目中求两个链表交点节点的指针。 注意:交点不是数值相等,而是指针相等。
  2. 两个链表长度不一致,难点在于A和B如何同时到达两个链表中的第一个公共节点。

参考:

leetCode题解

标签:面试题,02.07,相交,链表,headB,headA,节点,指针
From: https://blog.csdn.net/yuan_2001_/article/details/141300998

相关文章

  • 【142. 环形链表 II 中等】
    题目:给定一个链表的头节点head,返回链表开始入环的第一个节点。如果链表无环,则返回null。如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从0开始)。如......
  • 2024年Java面试题最新整理
    一、Java基础部分面试题1.Java面向对象的三个特征封装:对象只需要选择性的对外公开一些属性和行为。继承:子对象可以继承父对象的属性和行为,并且可以在其之上进行修改以适合更特殊的场景需求。多态:允许不同类的对象对同一消息做出响应。篇幅限制下面就只能给大家展示小册部分内容......
  • [LeetCode] 1367. Linked List in Binary Tree 二叉树中的链表
    Givenabinarytree root anda linkedlistwith head asthefirstnode.ReturnTrueifalltheelementsinthelinkedliststartingfromthe head correspondtosome downwardpath connectedinthebinarytree otherwisereturnFalse.Inthiscontext......
  • Java面试题———Redis篇①
    目录1、项目中为什么用Redis2、Redis的数据类型有哪些3、Redis为什么这么快4、Redis的过期删除策略有哪些5、Redis的内存淘汰策略有哪些6、Redis的RDB和AOF区别7、RDB期间可以同时处理写请求吗8、Redis集群有哪些方案1、项目中为什么用Redis我们项目中之所以选择R......
  • Java面试题———JVM篇
    目录1、JVM的主要组成部分有哪些2、堆栈的区别是什么3、JVM的类加载器有哪些4、什么是双亲委派模型5、说一下类加载器的执行过程6、怎么判断对象是否可以被回收7、JVM的垃圾回收算法有哪些8、JVM的垃圾回收器都有哪些1、JVM的主要组成部分有哪些JVM主要分为下面几......
  • 最新版Java面试题及答案整理(程序员必备)
    1、java为什么要有包装类型?主要原因包括以下几点:处理基本数据类型的null值:基本数据类型(如int,double等)不能直接赋值为null,而包装类型(如Integer、Double)可以表示null值,这对于某些业务逻辑和数据处理来说非常有用。提供额外功能:包装类型提供了一些额外的方法和功能,这些......
  • 全网最新200道Java程序员面试题(含答案)!
    发现网上很多Java面试题都没有答案,所以花了很长时间搜集整理出来了这套Java面试题大全~这套互联网30w字Java面试题包括了:MyBatis、ZK、Dubbo、EL、Redis、MySQL、并发编程、Java面试、Spring、微服务、Linux、Springboot、SpringCloud、MQ、Kafka 面试专题一、Java基础1.......
  • Java集合相关面试题(超详细)附:Java详细面试资料直链
    Java集合相关面试题内容搬运资料,来源见文章末尾仅为分享,不涉及任何获利行为,~(~ ̄▽ ̄)~可别发律师函啊链接:面试资料提取码:s4w8ArrayList底层实现是数组LinkedList底层实现是双向链表HashMap的底层实现使用了众多数据结构,包含了数组、链表、散列表、红黑树等1算法复杂度分......
  • 单链表
    //单链表#include<iostream>usingnamespacestd;constintN=1010;inthead,e[N],ne[N],idx;//初始化voidinit(){ head=-1; idx=0;}//插入voidadd_to_head(intx){ e[idx]=x; ne[idx]=head; head=idx; idx++;}//将x插到下标为k的点的后面voidadd(......
  • leetcode 21.合并两个有序链表
    leetcode21.合并两个有序链表题目描述:将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。迭代法:思路:不断迭代,谁小指向谁publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){if(list1==null){......