首页 > 其他分享 >链表中环的入口结点

链表中环的入口结点

时间:2023-07-25 12:22:44浏览次数:50  
标签:结点 中环 head next 链表 second 节点 first

title: 链表中环的入口结点
date: 2023-07-25 11:57:00
tags:
- c/c++
categories:
- 算法
- 笔试
top:

链表中环的入口结点

题目来自acwing

题目(点击跳转)

给定一个链表,若其中包含环,则输出环的入口节点。

若其中不包含环,则输出null

数据范围

节点 val 值取值范围 [1,1000]。

节点 val 值各不相同。

链表长度 [0,500]。

样例

QQ截图20181202023846.png

给定如上所示的链表:
[1, 2, 3, 4, 5, 6]
2
注意,这里的2表示编号是2的节点,节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

思路:

双指针实现,定义两个指针,first和second,同时从链表头部开始走,first每次走一步,second每次走两步,当second遇到NULL时代表链表走到尽头,即没有环。当两个指针第一次相遇时,将first重置为头节点的位置,second位置不变,这时让两个指针都已每次一步的距离开始走,当两个指针再次相遇时,这个点就是环的入口。

证明:假设b点为环的起点,当first和second从a开始出发,当first走到b时,first走了距离x,second走过了first两倍的路程,即为2x,second可能在环上已经走过一圈以上,这次加入first再走y距离与second相遇,那么second走的距离即为2y,也就是说当first在b时,second与b的距离为y,那当second走出了b点距离为y时,在环上再走距离x必定可以回到b点,那么将first从头节点开始走x,此时与second第二次相遇即为环的开始节点。

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(!head || !head->next) return NULL;
        auto first = head, second = head;
        
        while(first && second) {
            first = first->next;
            second = second->next;
            if(second) second = second->next;
            else return NULL;
            if(first == second){
                first = head;
                while(first != second){
                    first = first->next;
                    second = second->next;
                }
                return first;
            }
        }
        return NULL;
    }
};

标签:结点,中环,head,next,链表,second,节点,first
From: https://www.cnblogs.com/hhhhuaz/p/17579577.html

相关文章

  • 题解 链表 (chain)
    题目链接首先考虑没有修改怎么做。两种做法。想到询问的形式为保留\(\gek\)的连通块个数,那么先将全部数字按照权值排序,然后从后往前做一遍并查集,并同时统计连通块的数量,在询问时只需二分找到第一个\(\gek\)的位置,将这个位置的答案输出即可。注意考虑答案为\(0\)的情况......
  • 运势计算:以双向链表实现: 解读运势
    1解读运势我们已经做了些什么?这一小节我们将能看到我们做了一些什么事情,还记得第一小节的链表查询函数吗?没错就是display,在第二小节中,我们将每次的爻变记录和爻值存入了链表,现在我们实现它以显示爻变的过程。///显示并返回链表的值func(this*dlist)display()[]int{......
  • LeetCode 热题 100 之 21. 合并两个有序链表
    题目将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例2:输入:l1=[],l2=[]输出:[]示例3:输入:l1=[],l2=[0]输出:[0]提示:两个链表的节点数目范围是[......
  • 数组(Array)和链表(List)
    推荐https://cloud.tencent.com/developer/article/2304343引言在Java编程中,数组(Array)和链表(List)是常用的数据结构,用于在内存中存储和组织数据。两者都有各自的特点和适用场景,本文将深入比较数组与链表的区别,并结合代码示例进行详细解释。数组(Array)定义和特点数组是一种固定......
  • 运势计算:以双向链表实现: 计算爻卦
    1.0准备开始我们先制定一个计算结构体,一切开始于此。我们首先需要知道参与计算的算子有多少,我们就按最常用的数49来制定。typeDataTaostruct{DefMeanmap[int]string//卦象坐标名称DefValuemap[int]string//卦象坐标值4个GuaData[]......
  • 代码随想录-链表-C++总结
    代码随想录(programmercarl.com)这次复习的主要目的还是熟练c++的基本语法知识,顺带过一下链表的典型题目印象深刻直接没做出来的有7.链表相交,没有想到先过一遍求出两条链表的长度,然后通过长度差的信息来get交点做的时候写出bug的有3.设计链表,涉及的基础思想还是比较多的,需......
  • 单链表的实现
    #include<stdio.h>#include<stdlib.h>//创建一个单链表structLNode//结点{intdata;//数据structLNode*next;//指向下个结点的指针};voidList_Print(structLNode*p)//自定义列表打印函数{while(p){......
  • 双向链表的实现
    //带头节点的双链表#include<stdio.h>#include<stdlib.h>typedefstructDNode{intdata;structDNode*prior;structDNode*next;}DNode;//初始化头结点DNode*Init_DLinkList(){DNode*L;L=(DNode*)malloc(sizeof(DNode));L->......
  • 剑指 Offer 35. 复杂链表的复制
    题目:/*//DefinitionforaNode.classNode{public:intval;Node*next;Node*random;Node(int_val){val=_val;next=NULL;random=NULL;}};*/classSolution{public:Node*copyRandomList(N......
  • go 循环链表
    packagemainimport("fmt")typeNodestruct{DataintNext*Node}typeCircularLinkedListstruct{Head*NodeTail*Node}funcNewCircularLinkedList()*CircularLinkedList{return&CircularLinkedList{}}func(l......