首页 > 其他分享 >142.环形链表plus

142.环形链表plus

时间:2023-03-18 16:23:08浏览次数:53  
标签:slow 142 fast next 链表 plus 节点 指针

142. 环形链表 II

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

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

不允许修改 链表。

示例 1:

img

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

img

输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

img

输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

提示:

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

解题思路

本题思路不难以理解,很容易就能够想到使用快慢指针来解决问题,但是比较难的一点就是如何确定入口,本题运用了一个数学解题思路

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示:

img

那么相遇时: slow指针走过的节点数为: x + y, fast指针走过的节点数:x + y + n (y + z),n为fast指针在环内走了n圈才遇到slow指针, (y+z)为 一圈内节点的个数A。

因为fast指针是一步走两个节点,slow指针一步走一个节点, 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2:

(x + y) * 2 = x + y + n (y + z)

两边消掉一个(x+y): x + y = n (y + z)

因为要找环形的入口,那么要求的是x,因为x表示 头结点到 环形入口节点的的距离。

所以要求x ,将x单独放在左面:x = n (y + z) - y ,

再从n(y+z)中提出一个 (y+z)来,整理公式之后为如下公式:x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的,因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢?

先拿n为1的情况来举例,意味着fast指针在环形里转了一圈之后,就遇到了 slow指针了。

当 n为1的时候,公式就化解为 x = z

这就意味着,从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点

也就是在相遇节点处,定义一个指针index1,在头结点处定一个指针index2。

让index1和index2同时移动,每次移动一个节点, 那么他们相遇的地方就是 环形入口的节点。

源代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 快慢指针
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇,此时从head和相遇点,同时查找直至相遇,比较巧妙
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};

标签:slow,142,fast,next,链表,plus,节点,指针
From: https://www.cnblogs.com/luketebo/p/17231032.html

相关文章

  • 面试题 02.07链表相交
    面试题02.07.链表相交给你两个单链表的头节点headA和headB,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回null。图示两个链表在节点c1开......
  • 双链表
    双链表双链表有两个指针,一个指向前一个指向后,数组模拟链表实现思想双链表有两个指针,一个指向前一个指向后,故定义三个数组\(l[N],r[N],val[N]\)\(l[N]指向的是当前......
  • 力扣 142 环形链表
    判断一个链表有无环,并且如果有环指出入环的位置。1、判断有无环是通过一快一慢指针来判断的。快的指针走每次走两步、慢的指针每次走一步,这样如果没有环的话他俩不会相遇......
  • 数据结构-->链表_01
    首次书写链表有关的知识,先来明确什么是链表?链表是一种物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的举一个形象化的现实生活中......
  • 【链表】复习/刷题 记录
    leetcode203.RemoveLinkedListElements/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode......
  • Mybatis-Plus查询投影详解
    查询投影的作用是在查询数据库时只返回所需的字段,而不是返回全部的字段。这样可以实现以下几个方面的作用:减少网络传输数据量:只返回需要的字段,可以减少从数据库服务器到......
  • day3 | 203. 移除链表元素,206. 反转链表,707. 设计链表
    203.移除链表元素 题目描述 给你一个链表的头节点head和一个整数val,删除链表中的那些存储的值为val的节点,并且返回新的头节点。 思路: 1.创建一个虚拟头节点,......
  • 力扣---24. 两两交换链表中的节点
    给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。示例1:输入:head=[1,2,3,4]输出:[2,1,......
  • 狂神说的MyBatisPlus笔记 -https://blog.csdn.net/weixin_43070148/article/details/1
    狂神说的MyBatisPlus笔记https://blog.csdn.net/weixin_43070148/article/details/127313367学习MyBatis-Plus之前要先学MyBatis–>Spring—>SpringMVC为什么要学它?MyB......
  • 力扣24 两两交换链表中的节点
    两两交换链表中的节点:先把一个链表分为两个链表,再把两个链表组成一个链表。注意最后可能有一个链表有剩余,但此时另一个链表的指针已经到了NULL,要再遍历一遍/提前记录(感觉......