LeetCode[141] [142] 环形链表I II

2023-12-28 00:36:22

141. 环形链表 - 力扣(LeetCode)

142. 环形链表 II - 力扣(LeetCode)

题解:

快慢指针题

从head开始,一个快指针,一次前进两步,一个慢指针,一次走一步

如果没有环,则快指针首先到达链表尾部,

如果有环,快慢指针肯定能相遇即fast=slow

141代码:

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(slow && fast && fast->next)//这里的slow可以不用判断
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) return true;
        }
        return false;
    }
};

对于142需要环的起点,需要找出其中规律,动手画一下,当slow与fast相等的时候,假设slow从head开始走了k步,那么此时fast走了2k步,fast多走的k步是链表环的大小,假设相遇时,环起点与相遇点的距离为n,则head距离环启动的距离为k-n,slow继续往前走,距离环起点的距离也为k-n,所以此时任意一个指针从head开始,每次前进一步,刚好在环起点与slow相遇。代码如下:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != nullptr && slow != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
            
            if(fast != nullptr)
                fast = fast->next;
            if(fast == slow)
                break;
        }
        if(fast == nullptr) return nullptr;
        fast = head;
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }    
        return fast;
    }
};

文章来源:https://blog.csdn.net/weixin_44872774/article/details/135249410
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。