Leetcode 141. Linked List Cycle(链表找环)

题意重述

链表找环 原题链接

解题思路
  1. 创建一个set集合存放节点地址,遍历链表的每一个节点,插入前与set集合中所有元素相比较,时间复杂度O(n^2)
  2. 快慢指针思想,步长分别为1和2,若两指针相遇即有环,且 相遇节点与环起点距离= 头结点与相遇节点距离(数学证明),细节上注意快指针在奇数无环链表的处理,时间复杂度为O(n)

代码示例:
/*
141. Linked List Cycle
142. Linked List Cycle II

Given a linked list, determine if it has a cycle in it.

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
*/

#include<bits/stdc++.h>
using namespace std;

struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};

class Solution
{
    public:
        bool hasCycle(ListNode *head) {
            std::set<ListNode*> nodeset;
            while(head)
            {
                if(nodeset.find(head)!=nodeset.end())
                {
                    return true;
                }else{
                    nodeset.insert(head);
                }
                head=head->next;
            }
            return false;
        }

        ListNode *detectCycle(ListNode *head) {
            std::set<ListNode*> nodeset;
            while(head)
            {
                if(nodeset.find(head)!=nodeset.end())
                {
                    return head;
                }else{
                    nodeset.insert(head);
                }
                head=head->next;
            }
            return NULL;
        }

        ListNode *detectCycle2(ListNode *head) {
            struct ListNode *fast=head;
            struct ListNode *slow=head;
            struct ListNode *meet=NULL;
            while(fast)
            {
                slow=slow->next;
                fast=fast->next;
                if(!fast) //无环且个数为奇数
                {
                    return NULL;
                }
                fast=fast->next;
                if(fast==slow)
                {
                    meet=fast;
                    break;
                }                
            }
            if(!meet) //无环
            {
                return NULL;
            }
            while(head && meet)
            {
                if(head == meet)
                {
                    return meet;
                }
                head=head->next;
                meet=meet->next;
            }
            return NULL;
        }
};

int main()
{
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);
    ListNode f(6);
    ListNode g(7);
    ListNode h(8);
    ListNode i(9);
    a.next=&b;
    b.next=&c;
    c.next=&d;
    d.next=&e;
    e.next=&f;
    f.next=&g;
    g.next=&h;
    h.next=&i;
    i.next=&f;
    Solution solution;
    struct ListNode *head = &a;
    bool hascycle = solution.hasCycle(head);
    if(hascycle)
    {
        cout<<"has cycle!"<<endl;
    }else{
        cout<<"has no cycle!"<<endl;
    }

    head = solution.detectCycle(&a);
    if(head)
    {
        cout<<"cycle start with "<<head->val<<endl;
    }

    head = solution.detectCycle2(&a);
    if(head)
    {
        cout<<"cycle start with "<<head->val<<endl;
    }
    return 0;
}
示例输出
has cycle!
cycle start with 6
cycle start with 6

发表评论

电子邮件地址不会被公开。 必填项已用*标注