带环链表的深入理解

椰

发布于 2024-04-30 21:24:39

610

发布于 2024-04-30 21:24:39

文章被收录于专栏：转自CSDN转自CSDN

什么是带环链表

带环链表，意思就是在一个单链表中，链表中纯在环形结构

给定一个链表，判断链表是否由环

141. 环形链表 - 力扣（LeetCode）

思路：

对于这个题，我们用快慢指针就可以解决，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表，带环则一定会在环中相遇，否则快指针率先走到链表的末尾。

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

扩展：

1.为什么快指针走两步，慢指针走一步就可以？

我们这么理解，快慢指针不同时进入环，快指针先进入环，然后慢指针再进入，当慢指针进入后，就和快指针形成了“追及相遇”问题，因为快指针比慢指针快，所有能追上慢指针，当追上慢指针后就返回true即可；

2.快指针走3步，4步，5步可以么？

答案是不一定

这里从数学层面来解释

给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回 NULL

struct ListNode* hasCycle(struct ListNode* head) {
    struct ListNode *slow = head, *quick = head;
    while (quick && quick->next) {
        slow = slow->next;
        quick = quick->next->next;
        if (slow == quick) {
            return quick;
        }
    }
    return NULL;
}

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* cyc = hasCycle(head); // 得到了环内的一个结点

    if (cyc == NULL) {
        return NULL;
    }
    while (1) {
        if (head == cyc) {
            return head;
        }
        head = head->next;
        cyc = cyc->next;
    }
}