首页 > 其他分享 >160.相交链表

160.相交链表

时间:2023-12-10 15:44:27浏览次数:48  
标签:temp 相交 链表 headB 哈希 160 节点

1.题目介绍

给你两个单链表的头节点 \(headA\) 和 \(headB\) ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 \(null\) 。

图示两个链表在节点 \(c1\) 开始相交

题目数据 保证 整个链式结构中不存在环。

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

自定义评测:

评测系统 的输入如下(你设计的程序 不适用 此输入):

  • \(intersectVal\) - 相交的起始节点的值。如果不存在相交节点,这一值为 \(0\)
  • \(listA\) - 第一个链表
  • \(listB\) - 第二个链表
  • \(skipA\) - 在 \(listA\) 中(从头节点开始)跳到交叉节点的节点数
  • \(skipB\) - 在 \(listB\) 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 \(headA\) 和 \(headB\) 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。

示例 2:

输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [1,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 。

提示:

  • \(listA\) 中节点数目为 \(m\)
  • \(listB\) 中节点数目为 \(n\)
  • \(1 <= m, n <= 3 * 10^{4}\)
  • \(1 <= Node.val <= 10^{5}\)
  • \(0 <= skipA <= m\)
  • \(0 <= skipB <= n\)
  • 如果 \(listA\) 和 \(listB\) 没有交点,\(intersectVal\) 为 \(0\)
  • 如果 \(listA\) 和 \(listB\) 有交点,\(intersectVal == listA[skipA] == listB[skipB]\)

进阶:你能否设计一个时间复杂度 \(O(m + n)\) 、仅用 \(O(1)\) 内存的解决方案?

2.题解

2.1 哈希集合Hash_set(不同于哈希映射Hash_map)

思路和算法

判断两个链表是否相交,可以使用哈希集合存储链表节点。

首先遍历链表 headA,并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB,对于遍历到的每个节点,判断该节点是否在哈希集合中:

如果当前节点不在哈希集合中,则继续遍历下一个节点;

如果当前节点在哈希集合中,则后面的节点都在哈希集合中,即从当前节点开始的所有节点都在两个链表的相交部分,因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点,返回该节点。

如果链表 headB 中的所有节点都不在哈希集合中,则两个链表不相交,返回 null。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode *> visited;
        ListNode *temp = headA;
        while (temp != nullptr){
            visited.insert(temp);
            temp = temp->next;
        }
        temp = headB;
        while (temp != nullptr){
            if (visited.count(temp)){
                return temp;
            }
            temp = temp ->next;
        }
        return nullptr;
    }
};

2.2 双指针法

思路

这题问题之处在于:我希望消除两指针相同于相交点的位置差,然后两指针同时前进直至相遇。
巧妙之处就在于:我遍历链表A+B和遍历链表B+A的总结点数是一样的
假设p1指针指向的A链表的在共同节点前的节点数少一个,那么在p1指针指向B链表第一个的时候,p2链表刚好指向A链表最后一个。在这里便消除了两链表于共同节点的节点数量差值,之后两指针分别指向B链表和A链表相对于共同节点前相同数量的节点位置上,共同向后推进即可。

代码

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

标签:temp,相交,链表,headB,哈希,160,节点
From: https://www.cnblogs.com/trmbh12/p/17892730.html

相关文章

  • 【JavaSE】数据结构(栈、队列、数组、链表)
    什么是数据结构?数据结构是计算机底层存储、组织数据的方式,是指数据相互之间是什么方式排列在一起的常见的数据结构栈、队列、数组、链表二叉树、二叉查找树、平衡二叉树、红黑树哈希表栈特点:先进后出队列特点:先进先出数组特点:有索引,内存连续优点:查询速度快O(1)缺点:增......
  • CF104160
    CF104160记\(dis(T,a,b)\)为在树\(T\)上\(a,b\)之间的距离。给定两棵各\(n\)个点的树\(T_1,T_2\),\(q\)次询问,每次给定两个数\(a,b\),询问\[\max_{i=1}dis(T_1,a,i)+dis(T_2,b,i)\]\(1\len\le10^5,1\leq\le5\times10^5\)我们对询问离线,在第一棵树上dfs,枚举......
  • 【LeetCode-中等-链表】两数相加
    这是个关于链表的题目,以前在C#中写代码时,对链表接触比较少,所以刚好接这个题目来更好的熟悉一下链表题目大概是这样的,给你两个非空的链表,表示两个非负的整数.它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字 =》首先我们来理解这句话是什么意思我们来看......
  • [LeetCode Hot 100] LeetCode23. 合并K个升序链表
    题目描述思路:优先队列使用优先队列这个数据结构,对于这个数据结构,我们不用去管内部是如何实现的,我们只要知道有这么一种数据结构能帮助我们将一堆数据塞到优先队列这一个黑盒中,然后我们可以获取这堆数中最小的值或者最大的值。代码一:/***Definitionforsingly-linkedlis......
  • LeetCode876. 链表的中间结点
    题目描述思路:快慢指针快指针一次走两步慢指针一次走一步当快指针到达末尾的时候,慢指针所指的就是链表的中点方法一:/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(......
  • 数据结构:单链表——定义、插入、删除
    1、查找元素查找第i个元素LNode*GetEleme_i(LinkListL,inti){if(i<1){returnNULL;}LNode*p;p=L;intj=0;while(p!=NULL&&j<i){p=p->next;j++;}returnp;}查找e元素的结点LNode*GetEleme_e(LinkList&L,ElementTypee){LNode*p;p=L;while......
  • C 语言实现抽象数据类型(ADT)之链表
    C语言实现抽象数据类型(ADT)之链表1什么是链表?(懂跳)C语言本身自带了很多基本数据类型,每种基本数据类型的变量总是代表着某个数据,比如:我们通常用整型变量来计数,用浮点型变量来保存价格这样的数据……intcount;doubleprice;而有时候我们需要表示的数据很复杂,比如我们想要......
  • H7-TOOL发布2.24固件,增加CMSIS-SVD解析,RTOS Trace链表,I2C/SPI从机,CANopen解析等,脱机烧
    H7-TOOL详细介绍(含操作手册):http://www.armbbs.cn/forum.php?mod=viewthread&tid=89934视频介绍:https://www.bilibili.com/video/BV1494y1j7mj【PC软件】V2.2.41.脱机烧录功能升级  -新增GD32C10x系列  -新增钜泉光电HT502x  -新增英飞凌TLE987x系列  -新......
  • 141. 环形链表
    给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从0开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识......
  • 第2章. 链表(LinkedList)
    链表链表是一种链式存储的线性表,所有元素的内存地址不一定是连续的。单向链表一、单向链表的设计1.1、不带虚拟头结点publicclassLinkedList<E>{//链表的节点数量privateintsize;//链表的头结点privateNode<E>first;//静态成员内部类:s......