数据结构初阶——环形链表

目录

一、什么是环形链表？

二、关于环形链表的一些问题 

1、如何判断一个链表是否为环形链表

（1）快慢指针

（2）思路

（3）代码

2、如何找到环形链表的环形入口结点

（1）问题概述

 （2）思路

（3）L  =  n * C - X 

（4）代码实现

---

一、什么是环形链表？

哈哈哈~~其实也就是带环的链表啦~~

或者是这样：

因此，环形链表有个特性，就是没有 tail，指针一旦进入环形部分，就是死循环，永远走不出来。 

二、关于环形链表的一些问题 

1、如何判断一个链表是否为环形链表

https://leetcode.cn/problems/linked-list-cycle/

（1）快慢指针

首先，对链表的操作基本都是靠指针去完成的，因此肯定需要一个指针去维护这个链表，但环形链表有一个很重要的特性：就是由于有环状结构，因此指针一旦进入环状，就会在一直在链表里面，永远走不出来。因此我们应该用两个指针，一个遍历速度快一点，另一个遍历速度慢一点，简称“快慢指针”。

（2）思路

引用快慢指针之后，一旦慢指针进入环，通过快慢指针的速度差，当快指针追上慢指针的时候，就代表链表是环状的，否则快指针一旦为空，就说明链表不是环状链表。

注意：这里的快慢指针的相对速度必须是 1 ！！！否则就可能出现移动次数除不尽的问题。就比如当相对速度是 2 ，但相对距离是奇数，那么移动次数就除不尽了，快指针就不会和慢指针相遇，而是直接超过慢指针。

（3）代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
bool hasCycle(struct ListNode *head) 
{
    /* 快慢指针 */
    if ((head == NULL) || (head->next == NULL))
    {
        return false;
    }
    else
    {
        struct ListNode *fast = head, *slow = head;
 
        while ((fast != NULL) && (fast->next != NULL))
        {
            fast = fast->next->next;
            slow = slow->next;
            
            if (fast == slow)
            {
                return true;
            }
        }
 
        return false;
    }
}

2、如何找到环形链表的环形入口结点

https://leetcode.cn/problems/linked-list-cycle-ii/

（1）问题概述

简单来说就是如何找到图中的这个位置：

 （2）思路

这里我们通过环形链表可以得出一些结论：

这里我们设起点到入口的距离是 L；入口到相遇点的距离为 X；链表的环型部分为 C；快指针速度为 2；慢指针速度为 1.

因此慢指针走的路程为：L + X。 

到了这里，你或许就会问，为什么慢指针一定会在一圈内被快指针追上呢？

针对这个问题，我们可以这么想：假设最坏的情况（即快慢指针最远的相对距离）为在慢指针刚到入口时快指针在它的前面，那么距离为 C - 1。因为这两个指针的相对速度为1，因此总共要移动 （C - 1）/ 1 次，因此慢指针的移动距离为：1 *（（C - 1）/ 1）< C。

言归正传，快指针走的路程为：n * C + X + L。

因此便有了如下等式：2（L + X）= n * C + X + L;

化简后就得出了如下结论：L  = n * C - X

（3）L  =  n * C - X 

这个式子是什么意思呢？其实就是说在相同的时间内，慢指针从起点走到入口时，快指针从相遇点（X处）开始走 n 圈，最后与慢指针相遇，且此时新的相遇点恰好是环形链表的入口处！！！

（4）代码实现

struct ListNode *detectCycle(struct ListNode *head)
 {
    struct ListNode *fast = head, *slow = head;
 
    while ((fast != NULL) && (fast->next != NULL))
    {
        /* 找相遇点 */
        fast = fast->next->next;
        slow = slow->next;
 
        if (fast == slow) /* 慢指针从起点出发，快指针从相遇点出发，速度都为1 */
        {
            slow = head;
 
            while (slow != fast)
            {
                slow = slow->next;
                fast = fast->next;
            }
 
            return slow;
        }
    }
    return NULL;
}