题解 | #NC4 判断链表中是否有环#

'''
/**

• Definition for singly-linked list.

• struct ListNode {

• int val;

• ListNode *next;

• ListNode(int x) : val(x), next(NULL) {}

• };

• /
  class Solution {
  public:
  bool hasCycle(ListNode *head) {

    set<ListNode*>s;
    while(head){
        if(s.find(head)!=s.end()){
            return true;
        }
        s.insert(head);
        head=head->next;
    }
    return false;

  }
  };
  '''
  '''
  /**

• Definition for singly-linked list.

• struct ListNode {

• int val;

• ListNode *next;

• ListNode(int x) : val(x), next(NULL) {}

• };

• /
  class Solution {
  public:
  /*
  快慢指针解决：慢指针每走一步，快指针每次走两步，如果相遇就说明有环，如果一个为空说明没有环

  */
  bool hasCycle(ListNode *head) {

    ListNode*slow=head,*fast=head,*meet=nullptr;
    while(fast){
        slow=slow->next;
        fast=fast->next;
        if(!fast)
            return false;
        fast=fast->next;
        if(fast==slow){
            return true;
        }
    }
   // if(meet==nullptr) return false;

  // while(head&&meet){
  // if(head==meet){
  // return true;
  // }
  // head=head->next;
  // meet=meet->next;
  // }

    return false;

  }
  };
  '''