benym的知识笔记 benym的知识笔记
🦮首页
  • Java

    • Java-基础
    • Java-集合
    • Java-多线程与并发
    • Java-JVM
    • Java-IO
  • Python

    • Python-基础
    • Python-机器学习
  • Kafka
  • Redis
  • MySQL
  • 分布式事务
  • Spring

    • SpringIOC
    • SpringAOP
🦌设计模式
  • 剑指Offer
  • LeetCode
  • 排序算法
🐧实践
  • Rpamis

    • Utils
    • Exception
    • Security
  • 归档
  • 标签
  • 目录
🦉里程碑
🐷关于
GitHub (opens new window)

benym

惟其艰难,才更显勇毅🍂惟其笃行,才弥足珍贵
🦮首页
  • Java

    • Java-基础
    • Java-集合
    • Java-多线程与并发
    • Java-JVM
    • Java-IO
  • Python

    • Python-基础
    • Python-机器学习
  • Kafka
  • Redis
  • MySQL
  • 分布式事务
  • Spring

    • SpringIOC
    • SpringAOP
🦌设计模式
  • 剑指Offer
  • LeetCode
  • 排序算法
🐧实践
  • Rpamis

    • Utils
    • Exception
    • Security
  • 归档
  • 标签
  • 目录
🦉里程碑
🐷关于
GitHub (opens new window)
  • 剑指Offer

    • 01背包问题详解
    • LeetCode-面试题17-打印从1到最大的n位数
    • LeetCode-面试题03-不修改数组找出重复的数字
    • LeetCode-面试题03-数组中重复的数字
    • LeetCode-面试题04-二维数组中的查找
    • LeetCode-面试题05-替换空格
    • LeetCode-面试题06-从尾到头打印链表
    • LeetCode-面试题09-用两个栈实现队列
    • LeetCode-面试题10-1-斐波那契数列
    • LeetCode-面试题10-2-青蛙跳台阶
    • LeetCode-面试题11-旋转数组的最小数字
    • LeetCode-面试题13-机器人的运动范围
    • LeetCode-面试题14-1-剪绳子
    • LeetCode-面试题14-2-剪绳子(大数)
    • LeetCode-面试题15-二进制中1的个数
    • LeetCode-面试题16-数值的整数次方
    • LeetCode-面试题18-删除链表的节点
    • LeetCode-面试题19-正则表达式匹配
    • LeetCode-面试题20-表示数值的字符串
    • LeetCode-面试题21-调整数组顺序使奇数位于偶数前面
    • LeetCode-面试题22-链表中倒数第k个节点
    • LeetCode-面试题24-反转链表
    • LeetCode-面试题25-合并两个排序的链表
    • LeetCode-面试题26-树的子结构
    • LeetCode-面试题27-二叉树的镜像
    • LeetCode-面试题29-顺时针打印矩阵
    • LeetCode-面试题31-栈的压入弹出序列
    • LeetCode-面试题32-1-从上到下打印二叉树
    • LeetCode-面试题32-2-从上到下打印二叉树
    • LeetCode-面试题32-3-从上到下打印二叉树
    • LeetCode-面试题35-复杂链表的复制
    • LeetCode-面试题36-二叉搜索树与双向链表
    • LeetCode-面试题37-序列化二叉树
    • LeetCode-面试题38-字符串的排列
    • LeetCode-面试题39-数组中出现次数超过一半的数字
    • LeetCode-面试题40-最小的k个数
    • LeetCode-面试题41-数据流中的中位数
    • LeetCode-面试题42-连续子数组的最大和
    • LeetCode-面试题43-1到n整数中1出现的次数
    • LeetCode-面试题44-数字序列中某一位的数字
    • LeetCode-面试题45-把数组排成最小的数
    • LeetCode-面试题47-礼物的最大价值
    • LeetCode-面试题48-最长不含重复字符的子字符串
    • LeetCode-面试题49-丑数
    • LeetCode-面试题50-第一次只出现一次的字符
    • LeetCode-面试题51-数组中的逆序对
    • LeetCode-面试题53-1-在排序数组中查找数字I
    • LeetCode-面试题33-二叉搜索树的后序遍历序列
    • LeetCode-面试题54-二叉搜索树的第k大节点
    • LeetCode-面试题55-1-二叉树的深度
    • LeetCode-面试题12-矩阵中的路径
    • LeetCode-面试题30-包含min函数的栈
    • LeetCode-面试题34-二叉树中和为某一值的路径
    • LeetCode-面试题46-把数字翻译成字符串
    • LeetCode-面试题55-2-平衡二叉树
    • LeetCode-面试题56-1-数组中数字出现的次数
    • LeetCode-面试题56-2-数组中数字出现的次数2
    • LeetCode-面试题57-和为s的两个数字
    • LeetCode-面试题58-1-翻转单词顺序
    • LeetCode-面试题58-2-左旋转字符串
    • LeetCode-面试题59-2-队列的最大值
    • LeetCode-面试题60-n个骰子的点数
    • LeetCode-面试题61-扑克牌中的顺子
    • LeetCode-面试题62-圆圈中最后剩下的数字
    • LeetCode-面试题63-股票的最大利润
    • LeetCode-面试题64-求1+2+到+n
    • LeetCode-面试题65-不用加减乘除做加法
    • LeetCode-面试题66-构建乘积数组
    • LeetCode-面试题67-把字符串转化成整数
    • LeetCode-面试题68-1-二叉搜索树的最近公共祖先
    • LeetCode-面试题68-2-二叉搜索树的最近公共祖先
    • LeetCode-面试题07-重建二叉树
    • LeetCode-面试题52-两个链表的第一个公共节点
    • LeetCode-面试题53-2-0到n-1中缺失的数字
    • LeetCode-面试题57-2-和为s的连续正数序列
    • LeetCode-面试题59-1-滑动窗口的最大值
    • LeetCode-面试题28-对称的二叉树
  • LeetCode

    • LeetCode-54-螺旋矩阵
    • LeetCode-67-二进制求和
    • LeetCode-83-删除排序链表中的重复元素
    • LeetCode-415-字符串相加
    • LeetCode-498-对角线遍历
    • LeetCode-724-寻找数组的中心索引
    • 动态规划问题——最长上升子序列(LIS)(一)
    • 动态规划问题——最长上升子序列(LIS)(二)
    • 动态规划问题——最长上升子序列(LIS)(三)
    • LeetCode-144-二叉树的前序遍历
    • LeetCode-94-二叉树的中序遍历
    • LeetCode-145-二叉树的后序遍历
    • LeetCode-53-最大子序和
    • LeetCode-392-判断子序列
    • LeetCode-303-区域和检索-数组不可变
    • LeetCode-2-两数相加
    • LeetCode-3-无重复字符的最长字串
    • LeetCode-4-寻找两个正序数组的中位数
    • LeetCode-5-最长回文字串
    • LeetCode-11-盛最多水的容器
    • LeetCode-15-三数之和
    • LeetCode-17-电话号码的字母组合
    • LeetCode-19-删除链表的倒数第N个节点
    • LeetCode-20-有效的括号
    • LeetCode-21-合并两个有序链表
    • LeetCode-22-括号生成
    • LeetCode-23-合并K个排序链表
    • LeetCode-31-下一个排列
    • LeetCode-32-最长有效括号
    • LeetCode-33-搜索旋转排序数组
    • LeetCode-34-在排序数组中查找元素的第一个和最后一个位置
    • LeetCode-39-组合总数
    • LeetCode-46-全排列
    • LeetCode-47-全排列2
    • LeetCode-51-N皇后
    • LeetCode-55-跳跃游戏
    • LeetCode-56-合并区间
    • LeetCode-62-不同路径
    • LeetCode-64-最小路径和
    • LeetCode-70-爬楼梯
    • LeetCode-72-编辑距离
    • LeetCode-75-颜色分类
    • LeetCode-76-最小覆盖字串
    • LeetCode-77-组合
    • LeetCode-78-子集
    • LeetCode-84-柱状图中最大的矩形
    • LeetCode-102-二叉树的层序遍历
    • LeetCode-104-二叉树的最大深度
    • LeetCode-105-从前序与中序遍历构造二叉树
    • LeetCode-107-二叉树的层次遍历2
    • LeetCode-114-二叉树展开为链表
    • LeetCode-121-买卖股票的最佳时机
    • LeetCode-128-最长连续序列
    • LeetCode-136-只出现一次的数字
    • LeetCode-142-环形链表2
    • LeetCode-143-重排链表
    • LeetCode-146-LRU缓存机制
    • LeetCode-152-乘积最大子数组
    • LeetCode-198-打家劫舍
    • LeetCode-199-二叉树的右视图
    • LeetCode-206-反转链表
    • LeetCode-207-课程表
    • LeetCode-215-数组中的第K个最大元素
    • LeetCode-221-最大正方形
    • LeetCode-226-翻转二叉树
    • LeetCode-236-二叉树的最近公共祖先
    • LeetCode-279-完全平方数
    • LeetCode-287-寻找重复数
    • LeetCode-300-最长上升子序列
    • LeetCode-309-最佳买卖股票时机含冷冻期
    • LeetCode-322-零钱兑换
    • LeetCode-328-奇偶链表
    • LeetCode-347-前K个高频元素
    • LeetCode-394-字符串解码
    • LeetCode-406-根据身高重建队列
    • LeetCode-413-等差数列划分
    • LeetCode-416-分割等和子集
    • LeetCode-438-找到字符串中所有字母异位词
    • LeetCode-448-找到所有数组中消失的数字
    • LeetCode-461-汉明距离
    • LeetCode-494-目标和
    • LeetCode-538-把二叉搜索树转换为累加树
    • LeetCode-543-二叉树的直径
    • LeetCode-560-和为K的子数组
    • LeetCode-567-字符串的排列
    • LeetCode-581-最短无序连续子数组
    • LeetCode-617-合并二叉树
    • LeetCode-704-二分查找
    • LeetCode-739-每日温度
    • LeetCode-747-至少是其他数字两倍的最大数
    • LeetCode-890-查找和替换模式
    • LeetCode-1143-最长公共子序列
    • LeetCode-1247-交换字符使得字符串相同
    • LeetCode-1367-二叉树中的列表
    • LeetCode-字符串排序
    • LeetCode-面试题02.02-返回倒数第k个节点
    • LeetCode-面试题17.16-按摩师
    • 获取满足指数的最长字符串
    • 数组的最多素数个数
    • 最小字典序字符串
    • LeetCode-1-两数之和
    • LeetCode-16-最接近的三数之和
    • LeetCode-679-24点游戏
    • LeetCode-141-环形链表
    • LeetCode-155-最小栈
    • LeetCode-160-相交链表
      • LeetCode-160-相交链表
        • 解题思路
        • Java代码
        • Java代码2
    • 判断一棵二叉树是否为二叉搜索树和完全二叉树
    • LeetCode-169-多数元素
    • LeetCode-234-回文链表
    • LeetCode-238-除自身以外数组的乘积
    • LeetCode-283-移动零
    • LeetCode-338-比特位计数
    • LeetCode-797-所有可能的路径
  • 排序算法

    • 常见排序算法总结
    • 冒泡排序
    • 基数排序
    • 堆排序
    • 希尔排序
    • 归并排序
    • 快速排序
    • 插入排序
    • 桶排序
    • 选择排序
  • 算法
  • LeetCode
benym
2020-07-11
目录

LeetCode-160-相交链表

# LeetCode-160-相交链表

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表**:**

      a1--->a2
             \
              \
               c1--->c2--->c3
              / 
             /  
b1--->b2--->b3               
1
2
3
4
5
6
7
1
2
3
4
5
6
7

在节点c1开始相交

示例1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
1
2
3
1
2
3

示例2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
1
2
3
1
2
3

示例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。
1
2
3
4
1
2
3
4

注意:

  • 如果两个链表没有交点,返回 null.
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

# 解题思路

方法1、快慢指针:

短链表的指针会先到达链表末尾,称为快指针,此时将短链表指针指向长链表头部,

当短链表到达末尾时,长链表还剩的节点就是长短链表的相差的个数n,

这个时候短链表和长链表继续向前走,当长链表的慢指针到达尾部的时候,快指针就会从长链表头部走n步,此时再将慢指针变为短链表头部,就能够使得长短链表开始的头部位置相同

继续往下遍历直到链表头部值相等,如果找完了都不相等则返回null

为什么判断空的时候不采用如tempA.next!=null,而是采用tempA!=null,因为当两个链表不相交的时候,直接采用next判断将让循环无限下去,而采用如tempA!=null的方式可以很好的结束死循环(一长一短的链表或者相同长度的链表终究会在一定次数内相等为空)。

方法2、HashSet:

哈希集合的思路很简单,先遍历一个链表,将链表中的所有值加入进去,之后遍历第二个链表。当链表中的元素无法加入到集合中时,则说明有相交,否则说明两个链表不相交。

# Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) return null;
        ListNode tempA = headA;
        ListNode tempB = headB;
        while(tempA!=tempB){
            if(tempA!=null){
                tempA = tempA.next;
            }else{
                tempA = headB;
            }
            if(tempB!=null){
                tempB = tempB.next;
            }else{
                tempB = headA;
            }
        }
        return tempA;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# Java代码2

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode temp = headA;
        HashSet<ListNode> set = new HashSet<>();
        while(temp!=null){
            set.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while(temp!=null){
            if(set.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
编辑 (opens new window)
#链表#Java#Easy
上次更新: 2022/11/18, 11:15:10
LeetCode-155-最小栈
判断一棵二叉树是否为二叉搜索树和完全二叉树

← LeetCode-155-最小栈 判断一棵二叉树是否为二叉搜索树和完全二叉树→

最近更新
01
SpringCache基本配置类
05-16
02
DSTransactional与Transactional事务混用死锁场景分析
03-04
03
Rpamis-security-原理解析
12-13
更多文章>
Theme by Vdoing | Copyright © 2018-2024 benym | MIT License
 |   |   | 
渝ICP备18012574号 | 渝公网安备50010902502537号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式