【数据结构OJ题】链表带环问题

素颜马尾好姑娘i 2023-10-12 22:15 38阅读 0赞

**目录**

1.判断链表是否带环

证明

2.寻找环的入口点

--------------------

## **1.判断链表是否带环** ##

[原题链接：力扣][Link 1]

![222c69e95f3d48f0b8b5c911a20e0c8a.png][]

**思路一**：先遍历一遍链表，计算出链表的长度，然后将长度除二，在遍历半个链表即可。但是这种方法效率比较低。

**思路二**：使用快慢指针，慢指针每次走1步，快指针每次走2步，当快指针走到末尾是，慢指针的位置就是链表中间位置。

下面我们使用思路二来完成题目：

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

### **证明** ###

**1.为什么快指针每次走两步，慢指针走一步可以追上？**

**2.快指针一次走3步，走4步，...n步行吗？**

**证明：**假设slow进环以后，fast和slow的距离是N

这时fast真正开始追击slow，fast一次走**2**步，slow一次走1步，他们之间的距离每次缩小1

![78ceb70635aa4ae19a9a1126745db638.png][]

假设slow进环以后，fast和slow的距离是N

这时fast真正开始追击slow，fast一次走**3**步，slow一次走1步，他们之间的距离每次缩小2

这时候要分情况讨论：

![9cab6249d9c646009d104c14795cc91c.png][]

## **2.寻找环的入口点** ##

**原题链接：**[力扣][Link 1]

> 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
> 
> 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
> 
> 不允许修改链表。

![9a6eb5525a1e4ff38f24aa4ce00cbf71.png][]

**方法一：**用一个指针从链表的头节点出发，另一个指针从链表相遇的节点出发，当这两个指针相遇时，说明它们到达了入口

下面是原理：

![171d89215d9b4db796d2ede0be38eec3.png][]

代码实现：

struct ListNode *detectCycle(struct ListNode *head) 
    {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow)
            {
               struct ListNode *meet=slow;
               while(meet!=head)
               {
                   meet=meet->next;
                   head=head->next;
               }
               return meet;
            }
        }
        //如果链表没有环就返回空
        return NULL;
    }

**方法二：可以将这个题转化成两个链表相交的问题。**

将meet的下一个节点设置成newHead，求出head到meet的长度n, newHead到meet的长度m, 再利用快慢指针，使长的链表先走fabs(m-n)次，再同时走，当两个指针想等时，就到达了环的入口。

![2b130f9474c949bf9dc3e640db73a082.png][]

代码实现：

struct ListNode* detectCycle(struct ListNode* head)
    {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
            {
                struct ListNode* meet = slow;
                struct ListNode* moveA = slow;
                struct ListNode* moveB = head;
    
                //计算两链表的长度
                int lenA = 0;
                int lenB = 0;
                while (moveA != meet)
                {
                    moveA = moveA->next;
                    lenA++;
                }
                while (moveB != slow )
                {
                    moveB = moveB->next;
                    lenB++;
                }
    
                //计算长度差
                int gab = fabs(lenA - lenB);
                
                struct ListNode* longList = head;
                struct ListNode* shortList = slow;
                if (lenA < lenB)
                {
                    longList = slow;
                    shortList = head;
                }
                //让长的链表先走
                while (gab--)
                {
                    longList = longList->next;
                }
    
                while (longList != shortList)
                {
                    longList = longList->next;
                    shortList = shortList->next;
                }
                return longList;
            }
        }
    
        //不相交返回空
        return NULL;
    }

很明显的看出来，使用方法二的代码比方法一要复杂的多

[Link 1]: https://leetcode.cn/problems/linked-list-cycle/
[222c69e95f3d48f0b8b5c911a20e0c8a.png]: https://img-blog.csdnimg.cn/222c69e95f3d48f0b8b5c911a20e0c8a.png
[78ceb70635aa4ae19a9a1126745db638.png]: https://img-blog.csdnimg.cn/78ceb70635aa4ae19a9a1126745db638.png
[9cab6249d9c646009d104c14795cc91c.png]: https://img-blog.csdnimg.cn/9cab6249d9c646009d104c14795cc91c.png
[9a6eb5525a1e4ff38f24aa4ce00cbf71.png]: https://img-blog.csdnimg.cn/9a6eb5525a1e4ff38f24aa4ce00cbf71.png
[171d89215d9b4db796d2ede0be38eec3.png]: https://img-blog.csdnimg.cn/171d89215d9b4db796d2ede0be38eec3.png
[2b130f9474c949bf9dc3e640db73a082.png]: https://img-blog.csdnimg.cn/2b130f9474c949bf9dc3e640db73a082.png