实战Leetcode(三)

Practice makes perfect！
在这里插入图片描述

实战一：
在这里插入图片描述

带环问题其实我们小学时就接触过，就比如在操场上比赛跑步的追击问题，这里也是一样，如果我们定义两个指针，一个快指针，一个慢指针，快指针走的快，一次走两步，慢指针一次走一步，那么如果有环的话这两个指针一定就会相遇。

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

实战二：
在这里插入图片描述

这个题是上道题的升级版本，不仅需要你判断还要你返回环的位置，我们如果两个指针在相遇点相遇了，慢指针从相遇点开始走，头结点从初始位置开始走，那么他们一定会在入环的位置相遇。想到这里我们这个题是不是就迎刃而解了呢。

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast=head;
    struct ListNode* slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            struct ListNode* meet=slow;
            while(meet!=head)
            {
                head=head->next;
                meet=meet->next;
            }
            return meet;
        }
    }
    return NULL;
}