链表求环

LeetCode 141. Linked List Cycle 142.Linked List Cycle II

已知链表中可能存在环，若有环返回环起始节点，否则返回NULL。

算法1:使用set求环起始节点

1.遍历链表，将链表中节点对应的指针(地址)，插入set
2.在遍历时插入节点前，需要在set中查找，第一个在set中发现的节点地址，即是链表环的起点。

class Solution{
public:
    ListNode * detectCycle(ListNode *head){
    std:: set<ListNode *> node_set;//设置node_set
    while(head){
    if(node_set.find(head) != node_set.end()){
    return head;
}
node_set.insert(head);//将节点插入node_set
head = head->next;
}
return NULL;//没有遇到环，则返回NULL
}
}

算法2:快慢指针赛跑

结论：从head和meet出发，两指针速度一样，相遇时即为环的起点

class Solution{
public:
    ListNode * detectCycle(ListNode *head){
    ListNode *fast = head;//快慢指针
    ListNode *slow = head;
    ListNode *meet = NULL;
    while(fast){
    slow = slow->next;
    fast = fast->next;
    if(!fast){
        return NULL;//如果遇到链表尾，返回NULL
    }
fast = fast->next;
   if(fast ==  slow){
      meet = fast;  
      break;
  }
}
if(meet == NULL){
  return NULL;  
}
while(head && meet){
    if(head == meet){
        return head;    
}
head = head->next;
meet = meet->next;
}
return NULL;
}

};

测试与Leetcode提交结果

int main(){
  ListNode a(1);
  ListNode b(2);
  ListNode c(3);
  ListNode d(4);
  ListNode e(5);
  ListNode f(6);
  ListNode g(7);
  a.next = &b;
  b.next = &c;
  c.next = &d;
  d.next = &e;
  e.next = &f;
  f.next = &g;
  g.next =&c;
  Solution solve;
  ListNode *node = solve.detectCycle(&a);
  if(node){
    printf("%d\n",node->val);
  else{
      printf("NULL\n");
  }  
return 0;
}

}