首页 > 其他分享 >【力扣hot100】160.相交链表

【力扣hot100】160.相交链表

时间:2024-03-30 15:59:37浏览次数:23  
标签:力扣 相交 链表 headB headA null 160 节点

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

图示两个链表在节点 c1 开始相交:

在这里插入图片描述

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

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

示例 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 。

提示:

  • List item
  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点,intersectVal 为 0
  • 如果 listA 和 listB 有交点,intersectVal == listA[skipA] == listB[skipB]

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


方法一:哈希集合

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    const visited=new Set()
    let temp=headA;
    // 遍历链表headA,并将链表headA中的每个节点加入哈希集合中
    while(temp !== null){
        visited.add(temp)
        temp=temp.next
    }
    temp=headB
    //遍历链表headB,对于遍历到的每个节点,判断该节点是否在哈希集合中
    while(temp!= null){
        if(visited.has(temp)){
            return temp
        }
        temp=temp.next
    }
    return null
}

思路

  • 若链表headB中当前遍历的节点在哈希集合中,则该节点的值和temp.next所指向的地址与headA中的节点都相同,所以此节点即为相交节点,返回即可。
  • 若链表head中所有节点都不在哈希集合中,则两个链表不相交,返回null

在这里插入图片描述


方法二:双指针法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
function getIntersectionNode(headA, headB) {
    if (headA === null || headB === null) return null;
    let pA = headA,
        pB = headB;
    while (pA !== pB) {
        pA = pA === null ? headB : pA.next;
        pB = pB === null ? headA : pB.next;
    }
    return pA;
}

用指针pA、pB遍历两个链表

  1. 指针 pA 指向 A 链表,指针 pB 指向 B 链表,依次往后遍历
  2. 如果 pA 到了末尾,则 pA = headB 继续遍历
  3. 如果 pB 到了末尾,则 pB = headA 继续遍历
  4. 比较长的链表指针指向较短链表head时,长度差就消除了
  5. 如此,只需要将最短链表遍历两次即可找到位置

确实想不到,这思路太强了

标签:力扣,相交,链表,headB,headA,null,160,节点
From: https://blog.csdn.net/Jerryqjr/article/details/137169574

相关文章

  • 天下三分明月夜,独有快慢指针法(链表面试题篇)
    本篇会加入个人的所谓‘鱼式疯言’❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言而是理解过并总结出来通俗易懂的大白话,小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.......
  • 力扣刷题 45.跳跃游戏 II
    目录题干解题思路题干给定一个长度为 n 的 0索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i+j] 处:0<=j<=nums[i] i+j<n返回到达 nums[......
  • 双向链表C++
    今天写了双向链表..........写的头好晕..........看来链表还是要多加练习这个双向链表完成了增删改查,并且最后销毁链表环境VScode#include<iostream>#include<cstring>usingnamespacestd;//结点类classNode{public:stringip;//客户端ipstringn......
  • 【力扣】300. 最长递增子序列(DFS+DP两种方法实现)
    目录题目传送最长递增子序列[DFS方法]DFS方法思路图思路简述代码大家可以自行考虑有没有优化的方法最长递增子序列[DP]方法DP方法思路图思路简述代码方案题目传送原题目链接最长递增子序列[DFS方法]DFS方法思路图思路简述对于序列中的每一个数字只有选择......
  • 数仓 - [03] 拉链表
      拉链表是一种特殊的数据结构,其应用场景十分广泛,主要如下:1、监控系统:拉链表可以完整地记录系统的运行状态,方便进行监控和分析。2、金融交易:在金融领域,拉链表可以记录每个交易的时间戳、交易金额、交易类型等信息,从而实现对金融风险的监控和控制。例如,可以通过拉链表查询某......
  • 20240328,位运算,可变数组,链表(我是真的没有听懂)
    位运算一,按位运算按位运算,把整数当作2进制的数字进行运算?&按位与,|按位或,~按位取反,^按位的异或,<<左移, >>右移1.1&按位与·如果(x)i==1并且(y)i==1,那么(x&y)=1否则的话(x&y)i=0按位与常用于两种应用:·让某一位或某些位为0:  x&0xFE·取一个数中的一段: x&......
  • 力扣HOT100热题宝典--第3节
    ......
  • 数据结构:实验二 单链表
    一、   实验目的掌握单链表的存储结构特点掌握单链表中的各种基本运算算法设计。二、   实验内容与要求   编写一个程序exp2-2.cpp,实现单链表的各种基本运算和下面main函数中的每一步功能。初始化单链表L;依次采用尾插法插入’a’,’b’,’c’,’d’,’e’五......
  • 力扣HOT100热题宝典--第1节
    ......
  • 【LeetCode】1607. 没有卖出的卖家
    题目表:Customer+---------------+---------+|ColumnName|Type|+---------------+---------+|customer_id|int||customer_name|varchar|+---------------+---------+customer_id是该表具有唯一值的列。该表的每行包含网上商城的每一位顾客的......