【基础算法】单链表的OJ练习(5) # 环形链表 # 环形链表II # 对环形链表II的解法给出证明(面试常问到)

简介: 【基础算法】单链表的OJ练习(5) # 环形链表 # 环形链表II # 对环形链表II的解法给出证明(面试常问到)

前言


本章的OJ练习相对于OJ练习(4)较为简单。不过,本章的OJ最重要的是要我们证明为何可以这么做。这也是面试中常出现的。


对于OJ练习(4):-> 传送门 <-,分割链表以一种类似于归并的思想解得,回文链表以一种巧妙复用前面OJ题的思想解得。


啰嗦一下:对于本章,最重要的是需要证明为什么这样做可以,所以我们不光要做出来OJ,还要能够理解并自行给出证明。


环形链表


  • 题目链接: ->传送门<-
  • 题目描述:给你一个链表的头节点 head ,判断链表中是否有环。如果链表中存在环 ,则返回 true 。 否则,返回 false

带环链表类似于下面这种结构:


1ec71b1fb9f84ac9b2373505f87ed896.png



是否有环,实际上就是链表的最后一个节点是否指向了链表其中的一个节点,如果有环,我们遍历一遍链表的话,会陷入死循环。那么我们该如何判断链表是否有环呢?

解题思路:


由于带环链表直接遍历会陷入死循环,也就是说会无限在环内遍历下去,因此,这里可以引出一个追击问题:用快慢指针遍历链表。


我们定义两个指针,分别是慢指针slow,快指针fast,这两个指针同时遍历链表,slow每次走一步,fast每次走两步。fast会先进入环然后在环内跑圈,当slow进入环后,这就是一个典型的追及问题了,slow每次在环内走一步,fast每次在环内走两步,两个指针的距离每次缩小1,最终fast会追上slow与slow指向同一节点。当两个指针相等时,就可以判断该链表带环,因此判断条件就是fast == slow (return true)。


如果链表不带环,fast最终会指向NULL的前一个结点或者就指向NULL。因此,整个判断过程就结束了。


52ec724acb6d4f7ba41aec53c7b96b6b.gif

1a174e1932e5437cb74095f83537a30b.gif


  • 可以看到,如果链表没有环,链表的结点个数为偶数时,fast是指向NULL结束,链表的节点个数为奇数时,fast是指向最后一个结点结束。

解题代码:

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) return true;
    }
    return false;
}


为什么快慢指针可以?


  • 快指针每次走两步,慢指针每次走一步,当两个指针都在环内的时候,就成了一个追击问题,两个指针的距离每次缩小一,最终快指针会追上慢指针,因此判断其有环。
  • 那假如快指针每次走三步,慢指针走一步呢?


我们将带环链表抽象成下图:



6fc231e495fb4aa8b9d797b13eb5330b.png

假设每次快指针走三步,慢指针每次走一步,当两个指针都进环后,此时的相对位置为:


8ca008d33041400294ed4d22e09405dd.png我们记此时慢指针slow与快指针fast的距离为N,慢指针每次走一步,快指针每次走三步,因此N每次减少2,于是就有:


N - 2

N - 4

N - 6

N - 8

.....

最终有两种情况:

😃. N = 1,然后再减2 -> -1

😉. N = 2,然后再减2 -> 0


如果N最后减为-1,那么再次追击,如果N最后减为0,则快指针等于慢指针,判断为true。所以得出:当N为奇数时,追不上;当N为偶数时,一定追得上。


如果追不上,最后fast会在slow的下一个位置,然后继续追击,那么,继续追击又是否追的上呢?


我们假设环的长度为C,那么此时再次追击两个指针的距离就为:C - 1,令T = C - 1,则:


T - 2

T - 4

T - 6

T - 8

.....

最终有两种情况:

😃. T = 1,然后再减2 -> -1

😉. T = 2,然后再减2 -> 0


因此,这里又有两种情况,有了前面的推导,这里不难得出,当C为偶数时,则C - 1(T)为奇数,此时继续追不上,并且下一次也是一样,所以这里会陷入死循环;当C为奇数时,则C - 1为偶数,此时是追的上的。因此,当C为偶数时,永远追不上,当C为奇数时,追的上。


所以,通过以上分析,快指针每次走三步,慢指针每次走一步不一定能判断是否为带环链表,可能会陷入死循环,尽管陷入死循环就说明带环。

那么快指针每次走4步,走5步,走n步呢?这里就不是我们该探讨的范围了,相信大家心里已经有答案了。


环形链表 II


  • 题目链接:->传送门<-
  • 题目描述:给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。注意:不允许修改链表。
  • 与上一题不同的是,这一题首先是要判断链表是否带环,然后在带环的基础上返回链表入环的第一个节点。类似于下图:



f2ffabde408a4e419dbbb887c51fecfb.png

解题思路:

  • 这里直接说做法:先以第一题的思路使用快慢指针找到快指针和慢指针相遇的那个点,然后一个指针从该点开始走,一个指针从头开始走,每次走一步,最终两个指针会在入环的第一个节点相遇,然后返回这个节点。

解题代码:

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next)
    {
      // 快指针每次走两步
        fast = fast->next->next;
        // 慢指针每次走一步
        slow = slow->next;
    // 如果找到相遇的那个点,就开始找入环的第一个节点
        if (slow == fast)
        {
            struct ListNode *cur = slow;
            // 一个从头开始走,一个从当前节点开始走
            while (cur != head)
            {
                head = head->next;
                cur = cur->next;
            }
            // 最终相遇的那个点就是入环的第一个节点
            return cur;
        }
    }
  // 如果链表不带环,就返回NULL
    return NULL;
}


证明:为什么一个指针从快慢指针相遇的那个点开始走,一个指针从头开始走,最终两个指针会在入环的第一个节点处相遇?

  • 假设快慢指针在pos位置相遇,设链表头到入环的第一个节点的距离为X, 入环的第一个节点到pos的距离为Ypos到入环的第一个节点的距离为L,整个环的周长为C


bc17b11b35ac44c59df7a0852fb108f2.png


由此,我们计算一下,当快慢指针在pos相遇时分别走了多长的距离:

😃 快指针:X + nC + Y;

😉 慢指针:X + Y;

😮 为什么快指针有个nC而不是C

😮 为什么慢指针没有C?

  • 快指针有个nC是因为:有可能这个环的长度比较短,在慢指针入环时,快指针已经在环内走了n圈了。
  • 慢指针没有C是因为:慢指针入环后最多只会走C - 1步,不可能出现在环内步数超过一圈的情况,因此慢指针没有C

因此由快指针每次走两步,慢指针每次走一步的特点可以得出下面这个公式:


X + nC + Y = 2(X + Y);

化简得:

X = nC - Y;

进一步化简得:

X = (n - 1)C + (C - Y);

最终得:

X = (n - 1)C + L;


94dc1dbf477142a2807bbacd1f68b38b.png

由此公式,当一个指针从pos开始走,他走了(n - 1)C,最终还是会在pos位置。而当(n - 1)C走完后,从头开始走的指针与入环的第一个节点的距离为L,与此时pos到入环的第一个节点的距离相等。因此,为什么这样的做法可以,以上就是答案。


写在最后


对于单链表的题目练习,最重要的是思路,我们在数据结构阶段要养成画图的习惯,因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。


感谢阅读本小白的博客,错误的地方请严厉指出噢!

相关文章
|
28天前
|
Java 编译器 程序员
Java面试高频题:用最优解法算出2乘以8!
本文探讨了面试中一个看似简单的数学问题——如何高效计算2×8。从直接使用乘法、位运算优化、编译器优化、加法实现到大整数场景下的处理,全面解析了不同方法的原理和适用场景,帮助读者深入理解计算效率优化的重要性。
31 6
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
2月前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)
|
2月前
|
算法
经典算法之链表篇(二)
经典算法之链表篇(二)
|
7月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
6月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
6月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
65 2
|
7月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
61 1