C语言 推理证明带环链表详细过程

目录
  • 什么是带环链表:
  • 判断链表是否带环:
  • 环形链表 I
  • 找带环形链表入环的第一个结点:
  • 环形链表 II

什么是带环链表:

带环链表是链表最后一个结点的指针域不是指向空指针,而是指向链表之前的结点,这样就形成了环状的链表结构。

如图所示:

判断链表是否带环:

那么问题来了,如何判断一个链表是否带环呢?

这里我们再次运用了快慢指针,但是快慢指针又该如何具体设置呢?

  • 判断思路:

先定义一个快指针fast,一个慢指针slow。

快指针一定是比慢指针先进环的,当slow进环时,fast指针便开始了追slow指针,当快指针和慢指针相遇的时候,快指针便追上了慢指针,此时就可以判断该链表是有环的,但凡快指针指向空就说明该链表是不带环的。

  • 那么快慢指针一次各走几步最合适呢?

假设slow刚进环时,fast与slow之间的距离为N,环的长度为C。

  • 这里我们要多组讨论一下:(先讨论有代表的两组)

1.slow一次走1步,fast一次走2步一定能追上吗?

2.slow一次走1步,fast一次走3步一定能追上吗?

…………………

图为当slow刚进环时,假设fast所在的位置:

1.slow一次走1步,fast一次走2步一定能追上吗?

每次追击,fast与slow之间的距离就缩小1,当距离N缩小为0的时候,便追上了。

N - 1,N - 2,N - 3,……,0

所以这种情况一定能追上。

2.slow一次走1步,fast一次走3步一定能追上吗?

每次追击,fast与slow之间的距离就缩小2,这里要对N进行讨论:

(1)当N为偶数时,N每次缩小2,当距离N缩小为0的时候,便追上了。

N - 2,N - 4,N - 6,……,0

(2)当N为奇数时,N每次缩小2,当距离N缩小为1的时候,下次追击二者距离扔缩小2,此时               fast就会超过slow,距离N变为 -1 ,也就是C - 1,这时又要对C  - 1进行讨论。

  • 当C - 1为偶数时就能追上。
  • 当C - 1为奇数时就扔会错过,N再次变成C - 1,那么就会永远错过也就永远追不上。

所以这种情况不一定能追上,有可能永远追不上。

3.slow一次走1步,fast一次走4步一定能追上吗?

每次追击,fast与slow之间的距离就缩小3,这里又要对N进行讨论:

(1)当N为3的倍数时,N每次缩小3,当距离N缩小为0的时候,便追上了。

N - 3,N - 6,N - 9,……,0

(2)当N不为3的倍数时,那么fast会与slow错过,至于错过时fast超过slow多少距离还需讨论               (超过的距离取决于一开始N的长度)。

  • 当追上后,fast超过slow距离为1时,此时fast追slow追击距离为N即(C - 1),此时又要对C - 1进行上述讨论,即C - 1是否为3的倍数的讨论。
  • 当追上后,fast超过slow距离为2时,此时fast追slow追击距离为N即(C - 2),此时又要对C - 2进行上述讨论,即C - 2是否为3的倍数的讨论。

所以这种情况只有当N为3的倍数的时候才能追得上。

综上:能不能追得上取决于两个指针之间的距离N和环的大小C。

下面提供一个结论个人小结:(仅供参考,可能存在局限性)

只要快慢指针的速度差是2的时候,就可能会出现永远追不上的问题。假设fast与slow的速度差为x,那么fast追赶slow一次,他们之间的距离就减少x,途中有可能刚好追上,也有可能错过。当错过的时候,fast在slow前面,这时fast超过slow的距离的取值只可能是在[1 ~ (x - 1)]之间(x取整数)。同时任意一个正整数,假设记作m,(m > x)当m整除一个整数x有余数时,对这个整数m减去[1 ~ (x - 1)]中任意一个值,总能找到一个值x,使得m - x的值能够整除x。所以无论环的长度为多长,假设环的长度为C,总有C减去[1 ~ (x - 1)]中任意一个值,使得C - x能够整除x并且没余数,既然没余数那就是刚好追上的情况。

当fast和slow的速度差为2时,即x = 2的时候,C - x,x属于[1 ~ (x - 1)],那么C - x就只能是C - 1,那么当C - 1去整除2的时候,如果C - 1为奇数,那么C - 1整除2必然有余数,并且余数为1,下次还是C - 1去整除2,还是会余1,所以这时fast就永远追不上slow。

总结:

设置fast一次走2步,slow一次走1步的时候最保险。 因为快慢指针相距N,每追击一次N就减1,总会减到0,N缩小到0就是追到了。

环形链表 I

环形链表

OJ链接

给你一个链表的头节点 head ,判断链表中是否有环。

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

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

示例 1:

输入:

head = [3,2,0,-4], pos = 1

输出:

true

解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:

head = [1,2], pos = 0

输出:

true

解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:

head = [1], pos = -1

输出:

false

解释:链表中没有环。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head)
{
    struct ListNode* fast, *slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)
        return true;
    }

    return false;
}

思路:

运用上述判断环形链表的结论,fast一次走2步,slow每次走1步,只要是环状就一定会追的到。

找带环形链表入环的第一个结点:

接下来更深层次的问题来了,带环链表环的入口该怎么找呢?

以后带环问题通常都用fast一次走2步,slow一次走1步。

当快指针追到慢指针时,假设相遇点为meet,slow指针和fast指针在如图所示的:

注意:

这里快指针一定是先进环,slow后进环。

slow指针进环后,在走一圈的时间内,一定是会被fast追上的 。

思路:

在是slow指针和fast指针,同时从head头开始走,直到在meet点相遇,又因为fast指针的速度为slow指针速度的二倍,那么就一定满足一个等式关系:

快指针走的距离 = 慢指针走的距离 * 2

还需讨论的是当slow进环时,fast在环内走了多久的问题:

  • 当L足够长而C很小时:slow进环时fast可能已经在环内走了好多圈了(假设为n圈)。
  • 当L很小而C足够大时:slow进环时fast可能在环内 连一圈还没走。

综合考虑之后再结合上述等式关系变得到下列等式:

L + nC + X = 2 * (L+ X)

化简得:

L = n * C - X

这个公式充分说明了,一个指针从head走,一个指针从相遇点meet走,并且每次都走一步,一     直走下去,它们最终会在环的入口点相遇!!!

环形链表 II

环形链表 II

OJ链接

给定一个链表的头节点  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

解释:链表中没有环。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head)
{
    struct ListNode* fast, *slow;
    slow = fast = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)
        {
            struct ListNode* meet = slow;
            while(head != meet)
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}

思路1:

先运用上述判断环形链表的结论找到相遇点,再运用上述找环形入口点的结论,就能轻松找到环的入口点。

思路2:

先运用上述判断环形链表的结论找到相遇点,再将相遇点断开,这时就变成了上一篇博客找相交链表公共结点的问题,示意图如下:

参考代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head)
{
    struct ListNode* fast, *slow;
    slow = fast = head;
    int len1 = 0,len2 = 0;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)
        {
            struct ListNode* shortList, *longList, *meet, *longTail, *shortTail;
            longList = longTail = head;
            meet = shortList = shortTail = slow->next;
            slow->next = NULL;
            while(shortTail)
            {
                shortTail = shortTail->next;
                len1++;
            }
            while(longTail)
            {
                longTail = longTail->next;
                len2++;
            }
            int gap = abs(len1 - len2);
            if(len1 > len2)
            {
                longList = meet;
                shortList = head;
            }
            while(gap--)
            {
                longList = longList->next;
            }
            while(shortList != longList)
            {
                longList = longList->next;
                shortList = shortList->next;
            }
            return longList;
        }
    }
    return NULL;
}

到此这篇关于C语言 推理证明带环链表详细过程的文章就介绍到这了,更多相关C语言 带环链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言 超详细模拟实现单链表的基本操作建议收藏

    目录 1 链表的概念及结构 2 链表的分类 3 链表的实现无头+单向+非循环链表增删查改实现 3.1 链表的定义 3.2 链表数据的打印 3.3 链表的尾插 3.4 链表空间的动态申请 3.5 链表的头插 3.6 链表的尾删 3.7 链表的头删 3.8 链表任意位置的前插入 3.9 链表任意位置的后插入 3.10 链表的任意位置的删除 3.11 链表的任意位置的前删除 3.12 链表的任意位置的后删除 3.13 链表的销毁 3.14 链表的总结 1 链表的概念及结构 概念:链表是一种物理存储结构

  • C语言数据结构超详细讲解单向链表

    目录 1.链表概况 1.1 链表的概念及结构 1.2 链表的分类 2. 单向链表的实现 2.1 SList.h(头文件的汇总,函数的声明) 2.2 SList.c(函数的具体实现逻辑) 2.2.1 打印链表 2.2.2 搞出一个新节点(为其他函数服务) 2.2.3 链表尾插 2.2.4 链表头插 2.2.5 链表尾删 2.2.6 链表头删 2.2.7 查找节点 2.2.8 在pos位置之前插入 2.2.9 在pos位置之后插入 2.2.10 删除pos位置 2.2.11 删除pos之后位置 2.

  • C语言结构体使用之链表

    目录 一.结构体的概念 二.结构体的用法 三.结构体数组和指针 四.结构体指针 五.包含结构体的结构体 六.链表 七.静态链表 八.动态链表 一.结构体的概念 比如说学生的信息,包含了学生名称.学号.性别.年龄等信息,这些参数可能有些是数组型.字符型.整型.甚至是结构体类型的数据.虽然这些都是不同类型的数据,但是这些都是用来表达学生信息的数据. 二.结构体的用法 1.struct 结构体名称 访问方法: 结构体变量名.成员 {undefined 成员1: 成员2: }: 2. typedef s

  • C语言复杂链表的复制实例详解

    目录 一.题目描述 示例1: 示例2: 示例3: 示例4: 二.思路分析 三.整体代码 总结 一.题目描述 请实现 copyRandomList 函数,复制一个复杂链表.在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null. 示例1: 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例2: 输

  • C语言数据结构实例讲解单链表的实现

    目录 1.单链表 2.单链表的实现 头文件 函数的实现 (1)打印链表 (2)动态申请结点 (3)尾插 (4)头插 (5)尾删 (6)头删 (7)查找 (8)在pos之前插入 (9)删除pos (10)在pos之后插入 (11)在pos后删除 (12)最后用完记得销毁 3.各功能的测试 这里我们来简单实现单链表的增删查找. 1.单链表 概念:链表是一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 . (链表和我们生活中最接近的就是火车了.) 2.单链

  • C语言实现无头单链表详解

    目录 链表的结构体描述(节点) 再定义一个结构体(链表) 断言处理 & 判空处理 创建链表 创建节点 头插法 打印链表 尾插法 指定位置插入 头删法 尾删法 指定位置删除 查找链表 删除所有指定相同的元素 总结 再封装的方式,用 c++ 的思想做无头链表 链表的结构体描述(节点) #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int DataType; //节点 typede

  • C语言实现带头双向循环链表

    目录 前言 1. 创建结构体 2.malloc新节点 3.创建哨兵位节点 4.尾插 5.打印 6.尾删 7.头插 8.在指定位置pos的前面进行插入 9. 删除指定位置pos节点 10.销毁链表 前言 在实际生活中最常用的就是这两种链表.无头单向非循环链表.和带头双向循环链表.无头单向非循环链表:结构简单,一般不会单独用来存数据.实际中更多是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.另外这种结构在笔试面试中出现很多.带头双向循环链表:结构最复杂,一般用在单独存储数据.实际中使用的链表数

  • C语言 推理证明带环链表详细过程

    目录 什么是带环链表: 判断链表是否带环: 环形链表 I 找带环形链表入环的第一个结点: 环形链表 II 什么是带环链表: 带环链表是链表最后一个结点的指针域不是指向空指针,而是指向链表之前的结点,这样就形成了环状的链表结构. 如图所示: 判断链表是否带环: 那么问题来了,如何判断一个链表是否带环呢? 这里我们再次运用了快慢指针,但是快慢指针又该如何具体设置呢? 判断思路: 先定义一个快指针fast,一个慢指针slow. 快指针一定是比慢指针先进环的,当slow进环时,fast指针便开始了追sl

  • C语言实现可增容动态通讯录详细过程

    目录 创建可自动扩容的通讯录 添加用户信息 删除用户信息 查找联系人 修改用户信息 以名字将用户排序 销毁通讯录 创建可自动扩容的通讯录 这里我们想实现通讯录自动扩容,不够了能扩大内存,变得稍微有点智能,就不得不用到开辟内存的函数malloc和realloc,这两个函数又和free离不开关系 所以这里我给大家简单的介绍一下这三个库函数 malloc:这个函数向内存申请一块连续可用的空间,并返回指向这块空间的指针 void *malloc( size_t size ); 如果开辟成功,则返回一个指

  • 利用C语言实现页面置换算法的详细过程

    目录 操作系统实验 页面置换算法(FIFO.LRU.OPT) 概念: 题目: 代码 总结 操作系统实验 页面置换算法(FIFO.LRU.OPT) 概念: 1.最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面:如无这样的页面存在,则选择最长时间不需要访问的页面.于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率. 2.先进先出置换算法(FIFO):是最简单的页面置换算法.这种算法的基本思想是:当需要淘汰一个页面时,总是选择

  • C语言基础应用处理学生打分 计算时间 最少硬币问题详细过程

    第一题: 最少硬币问题(简单版) 假设有三种面值的硬币,分别为10.5.1.接收一个整数作为金额数,计算要达到该金额数,每个面值的硬币最少需要多少枚. 输出结果演示: 参考答案: #include <stdio.h> typedef struct StructrueMoneyBox { int n10; int n5; int n1; } MoneyBox; int main(void) { MoneyBox change = {0, 0, 0}; int face_value[4] = {1

  • C语言数据结构与算法之链表(一)

    目录 引言 链表的相关思考 链表结点结构 建立链表 实现插入操作 完整代码 引言 在存储一大波数的时候,我们通常使用的是数组,但是数组有时候又会显得不够灵活,比如下面这个例子: 有一串已经排序好的数 2,3,5,8,9 ,10 如果我们想要往数组中插入6 这个元素,需要把 8 以后的元素全部往后挪一位 这样操作显然很耗费时间,如果使用链表的话则会快很多.那么什么是链表呢?请看下图: 此时如果需要在8前面加入一个6,那么只需要向下图一样更改一下就可以了,而不用向像最开始那样把每个数向后挪. 链表的

  • C语言深入探索之单链表与typedef的用法

    目录 前言 详解typedef关键字 含义 具体使用 详解单链表参数形式 指针知识补充 单链表形参详解 单链表实战案例 完整代码实现 详解头插建表 运行效果 前言 昨天博主去本站问答贴子逛了逛,然后发现了好多关于数据结构线性表,具体来说是单链表的问题.有的是没有一点思路,无从下手:有的是看不懂代码,不理解关键字以及被形参的形式气的不行,我总结了一下常见问题来给大家带来干货,到后面还有简单案例来巩固知识,弄透一题胜无脑刷百题,接下来是正文内容. 详解typedef关键字 含义 C语言允许用户使用

  • 详解C语言中二级指针与链表的应用

    目录 前言 二级指针讲解 链表的应用 定义双链表的结构体 创建双链表 前言 这篇文章即将解决你看不懂或者不会写链表的基本操作的问题,对于初学者而言,有很多地方肯定是费解的.比如函数的参数列表的多样化,动态分配内存空间函数malloc等,其实这些知识和指针联系紧密,尤其是二级指针.那么开始好好的学习这篇文章吧! 二级指针讲解 简述:其实就是一个指针指向另一个指针的地址. 我们都知道指针指向地址,但是指针自身也是一个变量,当然也可以被二级指针所指向. 语法:形如 int x = 10; int *q

  • C语言数据结构中约瑟夫环问题探究

    目录 问题描述 基本要求 测试数据 实现思路1 实现思路2 结果 数据结构开讲啦!!! 本专栏包括: 抽象数据类型 线性表及其应用 栈和队列及其应用 串及其应用 数组和广义表 树.图及其应用 存储管理.查找和排序 将从简单的抽象数据类型出发,深入浅出地讲解复数 到第二讲线性表及其应用中会讲解,运动会分数统计,约瑟夫环,集合的并.交和差运算,一元稀疏多项式计算器 到最后一步一步学会利用数据结构和算法知识独立完成校园导航咨询的程序. 希望我们在学习的过程中一起见证彼此的成长. 问题描述 约瑟夫环问题

  • C语言哈希表概念超详细讲解

    目录 1. 哈希概念 2. 哈希冲突 3. 哈希实现 3.1 闭散列(哈希表) 3.1.1 闭散列的细节 3.1.2 优化后的闭散列 3.2 扩散列(哈希桶) 3.2.1 扩散列的细节 4. 哈希表和哈希桶的比较 5. 结尾语 1. 哈希概念 哈希其实在学排序时已经用过了,就是计数排序.计数排序也是用的一种映射关系. 比如对此数组进行 计数排序 :1 1 9 9 9 3 3 8 8 我用的是绝对映射 ,所以开辟的数组空间 它的大小 必须 能映射到 最大的元素. 但是 对于哈希来讲,可以用决定映射

  • C语言实现带头结点的链表的创建、查找、插入、删除操作

    本文实例讲述了C语言实现带头结点的链表的创建.查找.插入.删除操作.是数据结构中链表部分的基础操作.分享给大家供大家参考.具体方法如下: #include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next;// 这个地方注意结构体变量的定义规则 } Node, *PNode; Node* createLinklist(int length) { int i = 0; PNo

随机推荐