如何通过C++求出链表中环的入口结点

目录
  • 题目描述：
  • 输入描述：
  • 返回值描述：
  • 示例：
  • 解题思路：
  • 测试代码：

题目描述：

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n≤10000，1<=结点值<=10000

要求：空间复杂度 O(1)，时间复杂度 O(n)

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

返回值描述：

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例：

输入：

{1,2},{3,4,5}

返回值：

3

说明：

返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3

解题思路：

本题考察数据结构链表的使用，有两种解法。

  1. 哈希Set。用容器哈希Set遍历存储指针，当某次存储发现容器中已有该指针，说明此时已经到了环形链表入口。
  2. 快慢双指针法。如下图所示，快指针以慢指针两倍的速度前进，当他们第一次相遇时，慢指针走了X+Y，快指针走了2*(X+Y)，其中AB为X，BC为Y，那CB顺指针的距离就是2*(X+Y)-X-2*Y=X，此时将快指针放到头节点A处，让它们以相同速度前进，到B时正好相遇，也就是入口结点。

测试代码：

解法一：哈希Set

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        unordered_set<ListNode*> S;
        while(pHead)
        {
            if(S.find(pHead)= = S.end())
            {
                S.insert(pHead);
                pHead = pHead->next;
            }
            else{
                return pHead;
            }
        }
        return nullptr;
    }
};

解法二：快慢双指针 

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        // 空指针返回
        if(pHead == nullptr)
            return nullptr;

        // 定义双指针
        ListNode* slow = pHead;
        ListNode* fast = pHead;

        // 当能形成闭路时，while才会无限循环直到break
        while(fast != nullptr && fast->next != nullptr)
        {
            // 快指针以两倍速度前进
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast)
                break;
        }

        // 若指向空指针，说明没有形成闭路
        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        // 将快指针指向头
        fast = pHead;

        // 当他俩相遇时，就是环形链表入口处
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }

        return fast;
    }
};

到此这篇关于如何通过C++求出链表中环的入口结点的文章就介绍到这了,更多相关C++ 链表中环的入口结点内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++相交链表和反转链表详解

    C++相交链表和反转链表详解

    目录 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点.如果两个链表没有交点,返回 null . 思路 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表. 双指针思路 递归 总结 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点.如果两个链表没有交点,返回 null . 思路 简单来说,就是求两个链表交点节点的 指针. 这里同学们要注意,交点不是数值相等,而是指针相等. 为了方便举例,假设节点

  • C++解决合并两个排序的链表问题

    C++解决合并两个排序的链表问题

    目录 题目描述: 示例: 解题思路: 测试代码: 题目描述: 输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的. 数据范围: n为0~1000,节点值为-1000~1000 要求:空间复杂度 O(1),时间复杂度 O(n) 如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},转换过程如下图所示: 或输入{-1,2,4},{1,3,4}时,合并后的链表为{-1,1,2,3,4,4},所

  • C++ 解决求两个链表的第一个公共结点问题

    C++ 解决求两个链表的第一个公共结点问题

    目录 题目描述: 输入描述: 返回值描述: 示例: 解题思路: 题目描述: 输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空.(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的) 数据范围: n<=1000 要求:空间复杂度 O(1),时间复杂度 O(n) 例如,输入{1,2,3},{4,5},{6,7}时,两个无环的单向链表的结构如下图所示: 可以看到它们的第一个公共结点的结点值为6,所以返回结点值为6的结点. 输入描述: 输入分

  • C++实现LeetCode(237.删除链表的节点)

    [LeetCode] 237.Delete Node in a Linked List 删除链表的节点 Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with va

  • C++实现LeetCode(160.求两个链表的交点)

    [LeetCode] 160.Intersection of Two Linked Lists 求两个链表的交点 Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A:          a1 → a2 c1 → c2 → c3             B:     b1

  • 带你了解如何用C++合并两个有序链表

    带你了解如何用C++合并两个有序链表

    目录 将两个升序链表合并为一个新的 升序 链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. 思路 代码 链表Listnode详细介绍 总结 将两个升序链表合并为一个新的 升序 链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] 示例 3: 输入:l1 = [], l2 = [0] 输出:[0] 思路 可以简

  • 如何通过C++求出链表中环的入口结点

    如何通过C++求出链表中环的入口结点

    目录 题目描述: 输入描述: 返回值描述: 示例: 解题思路: 测试代码: 题目描述: 给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null. 数据范围: n≤10000,1<=结点值<=10000 要求:空间复杂度 O(1),时间复杂度 O(n) 例如,输入{1,2},{3,4,5}时,对应的环形链表如下图所示: 可以看到环的入口结点的结点值为3,所以返回结点值为3的结点. 输入描述: 输入分为2段,第一段是入环前的链表部分,第二段是链表环的部分,后台会根据第二段

  • PHP实现找出链表中环的入口节点

    本文实例讲述了PHP实现找出链表中环的入口节点.分享给大家供大家参考,具体如下: 问题 一个链表中包含环,请找出该链表的环的入口结点. 解决思路 第一步,找环中相汇点.分别用p1,p2指向链表头部,p1每次走一步,p2每次走二步,直到p1==p2找到在环中的相汇点. 第二步,找环的入口.接上步,当p1==p2时,p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数,再让p2指向链表头部,p1位置不变,p1,p

  • 矩形相交以及求出相交的区域的原理解析

    矩形相交以及求出相交的区域的原理解析

    (1)设计一个算法,确定两个矩形是否相交(即有重叠区域) (2)如果两个矩形相交,设计一个算法,求出相交的区域矩形 (1) 对于这个问题,一般的思路就是判断一个矩形的四个顶点是否在另一个矩形的区域内.这个思路最简单,但是效率不高,并且存在错误,错误在哪里,下面分析一 下. 如上图,把矩形的相交(区域重叠)分成三种(可能也有其他划分),对于第三种情况,如图中的(3),两个矩形相交,但并不存在一个矩形的顶点在另一个矩形 内部.所以那种思路存在一个错误,对于这种情况的相交则检查不出. 仔细观察上图,想

  • Python求出0~100以内的所有素数

    质数又称素数.一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数:否则称为合数. 一.判断一个数是否为素数: 基于定义 def is_prime(num): if num <= 1: return '%d是一个合数' % num for i in range(2, num): if not num % i: return '%d是一个合数' % num else: return '%d是一个素数' % num 考虑合数的性质 def is_prime(num): if num

  • Java读取一行空格隔开的数字字符串并求出这些数字的和方法

    如下所示: import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while(in.hasNextLine())//判断是否有输入一行数据 { String tmp = in.nextLine();//将一行数据读出 if(tmp.equals("q"))//输入q退出程序 break; Str

  • Python二维数组实现求出3*3矩阵对角线元素的和示例

    题目:求一个3*3矩阵对角线元素之和. 程序分析:利用双重for循环控制输入二维数组,再将a[i][i]累加后输出. def two_dimensionalArray(self): '二维数组实现求三阶矩阵的对角线元素之和' sum = 0 matrix = [[0, 1, 0], [0, 21, 0], [0, 12, 0]] matrix2 = [[0 for i in range(3)] for i in range(3)] matrix2[0][0] = 123 matrix2[1][1

  • python 对任意数据和曲线进行拟合并求出函数表达式的三种解决方案

    第一种是进行多项式拟合,数学上可以证明,任意函数都可以表示为多项式形式.具体示例如下. ###拟合年龄 import numpy as np import matplotlib.pyplot as plt #定义x.y散点坐标 x = [10,20,30,40,50,60,70,80] x = np.array(x) print('x is :\n',x) num = [174,236,305,334,349,351,342,323] y = np.array(num) print('y is

  • Python递归求出列表(包括列表中的子列表)的最大值实例

    要求:求出列表中的所有值的最大数,包括列表中带有子列表的. 按照Python给出的内置函数(max)只能求出列表中的最大值,无法求出包括列表中的子列表的最大值 Python3代码如下: #!/usr/bin/env python3 # _*_ coding:UTF-8 _*_ list_tmp = [1,3,5,7,9,11] print(max(list_tmp)) 返回的结果为:11 按照Python3给出内置函数(max)的方法想要违和他的要求求出列表包括子列表的数,他就会给你进行报错.

  • SQL查询语句求出用户的连续登陆天数

    SQL查询语句求出用户的连续登陆天数

    一.题目描述 求解用户登陆信息表中,每个用户连续登陆平台的天数,连续登陆基础为汇总日期必须登陆,表中每天只有一条用户登陆数据(计算中不涉及天内去重). 表描述:user_id:用户的id: sigin_date:用户的登陆日期. 二.解法分析 注:求解过程有多种方式,下述求解解法为笔者思路,其他解法可在评论区交流. 思路: 该问题的突破的在于登陆时间,计算得到连续登陆标识,以标识分组为过滤条件,得到连续登陆的天数,最后以user_id分组,以count()函数求和得到每个用户的连续登陆天数. 连

  • Java求出任意数字的各个位数之和方式

    目录 求出任意数字的各个位数之和 求一个整数各位数之和 思路分析 代码 求出任意数字的各个位数之和 import java.util.Scanner; /** * 用JAVA求任意一个数的各个位数之和 * @author Administrator * */ public class test { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("请输入一

随机推荐