代码编织梦想

142. 环形链表 II

中等

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。

示例 1:
在这里插入图片描述
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
在这里插入图片描述
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
在这里插入图片描述
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

提示:
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

方法一:快慢指针

在这里插入图片描述
由上图可知:
(1)当slow和fast在P点相遇时,重新建立节点K=A,节点W=P.速度都与slow相同
(2)K->F的路程为(N-1)*C+X;
W->F路程:X;
(3)W走了(N-1)*C后,又回到了相遇点,W->F距离为X;
K也走了(N-1)*C,距离F也为X;
(4)在这时,他们就能在环的第一个节点处相遇

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(slow != null && fast != null&& fast.next != null){
            slow = slow.next;//一次走一步
            fast = fast.next.next;//一次走两步
            //找到相遇点时
            if(slow == fast){
               ListNode circleFirst = head;
               while(circleFirst != slow){
                   circleFirst = circleFirst.next;
                   slow = slow.next;
               }
               return circleFirst;
            }
        }
        return null;
    }
}

方法二:哈希表

我们遍历链表中的每个节点,并将它记录下来;一旦遇到了此前遍历过的节点,就可以判定链表中存在环。
万一有人迷糊,可能有人要问了,如果一个链表中有相同数值的节点,并且不构成环,那不是错了么.实际上就算节点的值相同,但是他们的地址是不一样的,而我们比较的就是地址,每一个位置都是唯一的.第一次走过的地方,走过后又经过了这里,那不就是在兜圈子吗,就找到了兜圈子的起点.

public class Solution {
    public ListNode detectCycle(ListNode head) {
       Set<ListNode> set = new HashSet<>();
       ListNode cur = head;
       while(cur != null){
           if(set.contains(cur)){
               return cur;
           }else {
               set.add(cur);
           }
           cur = cur.next;
       }
       return null;
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_51866806/article/details/129816946

LeetCode 142. 环形链表 II-爱代码爱编程

写在前面: 这道题有很多解法,不乏一些心机解法,比如在内存充足情况下(正常来讲是充足的)利用链表内存顺序存取,堆的地址又是从低到高,如果链表有环,则head->next小于或者等于head。比较正常的解法应该会用到set这种数据结构,我这题是纯用数学方法。 定义快慢指针指向头结点,快指针速度是慢指针两倍设头结点到环的起点距离为a,环的起点到两指针第

Leetcode 142. 环形链表 II-爱代码爱编程

Leetcode 142. 环形链表 II 1、问题分析2、问题解决3、总结 1、问题分析 题目链接:https://leetcode-cn.com/problems/linked-list-cycle-ii/   本质上就是一个快慢指针判断环问题。代码我已经进行了详细的注释,理解应该没有问题,读者可以作为参考,如果看不懂(可以多看几遍),欢

【链表】142. 环形链表 II-爱代码爱编程

题目: 题意: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。 说明:不允许修改给定的链表。 题解: 步骤: (1)判断链表是否环 使用快慢指针法,分别定义 fast

142.环形链表II-爱代码爱编程

题目 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不

链表篇 142. 环形链表 II-爱代码爱编程

环形链表 II(难度 中等)给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有

力扣 142.环形链表ii-爱代码爱编程

142. 环形链表 II - 力扣(LeetCode) 给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 p

leetcode——138. 复制带随机指针的链表-爱代码爱编程

🐨目录 📑1. 题目🦨2. 解法1 - 暴力求解🥦2.1 思路🥦2.2 代码实现 🦋3. 解法2 - 拆分节点🥕3.1 思路🥕3.2 代码实现 📑1. 题目 给你一个长度为 n的链表,每个

力扣:142. 环形链表 ii_力扣环形链表二-爱代码爱编程

题目链接:142. 环形链表 II 题目: 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则

142.环形链表 ii_142. 环形链表 ii-爱代码爱编程

1、哈希表 当链表访问到一个节点的时候,在对应的哈希表中查找此节点是否出现过,若出现过,则说明当前节点就是环形链表的头节点,否则查找下一个节点,若最终找到NULL(nullptr)则说明,在此链表中没有环,返回NULL 代码如下: class Solution { public: ListNode *detectCycle(ListNod

【leetcode刷题】142. 环形链表 ii-爱代码爱编程

1:题目描述(力扣) 给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环

算法 哈希表2 || 第454题.四数相加ii || 383. 赎金信 || 第15题. 三数之和 || 第18题. 四数之和_juafh-爱代码爱编程

第454题.四数相加II 和两数之和很相似,直接把四个数组分为两个大组。A+B的每一种可能以及出现的次数放进map,再去找 0-(c+d),每找到一次count计数,要加上0-(c+d)这个k对应的value值,而不是++

对于并发的学习-爱代码爱编程

ThreadLocal对象可以提供线程局部变量,每个线程Thread拥有一份自己的副本变量,多个线程互不干扰。 ThreadLocal的数据结构 Thread类有一个类型为ThreadLocal.ThreadLocalMap的实例变量threadLocals,也就是说每个线程有一个自己的ThreadLocalMap。 ThreadLocalMap

18-爱代码爱编程

题目 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交: 题目数据保证整个链式结构中不存在环。 注意,函数返回结果后,链表必须 保持其原始结构 。 自定义评测: 评测系统的输入如下(你设计的程序不适用此输入):

代码随想录算法训练营第四十一天| 343. 整数拆分 96.不同的二叉搜索树-爱代码爱编程

343. 整数拆分 题目链接 思路: 动态规划 动规5步曲: 1、确定dp数组及其下标含义: dp[i]: 拆分数字 i ,可以得到的最大乘积为dp[i] 2、确定递推公式 从 1 开始遍历 j 然后两种方式得到d

b+tree-爱代码爱编程

前言 B+树中的B代表平衡(balance),而不是二叉(binary),因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉树(Binary Tree)、二叉查找树(Binary Search Tree)、平衡二叉树(AVLTree)和平衡多路查找树(B-Tree),B+树(B+Tree)即由这些树逐步优化而来。 基本概念

树、二叉树、堆-爱代码爱编程

目录 一、树的表示 二、二叉树的概念及结构 1、概念: 2、特殊的二叉树 3、二叉树的存储结构  三、堆 1、大\小根堆 2、堆的实现 1)结构及初始化  2)插入 3)删除 4)取堆顶数据 5)判空 6)大小 7)销毁 四、堆排序 一、树的表示 常用:孩子兄弟表示法 typedef int DataT