MENU

Linked list cylce-ii 解法

该题目要求找到单链表里面的环开始的位置,解法如下:

#include <iostream>

#include <set>

using namespace std;

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

 set<ListNode *> v;

    ListNode *detectCycle(ListNode *head) {
  if(!head)
   return NULL;
  ListNode *slow=head;
  ListNode *fast=head;

  while(fast->next)
  {
   fast=fast->next;
   if(fast->next)
   {
    slow=slow->next;
    fast=fast->next;
   }

   if(fast==slow)
   {
    while(1)
    {
     v.insert(fast);
     fast=fast->next;
     if(fast==slow)
      break;
    }
    break;
   }
  }

  if(v.empty())
   return NULL;
  
  fast=head;
  while(fast->next)
  {
   if(v.find(fast)!=v.end())
    return fast;
   fast=fast->next;
  }
    }
};

int main()
{
 Solution s;
 ListNode *l,*cur;
 int a;

 for(int i=0; i<1; i++)
 {
  cin >> a;
  if(!i)
   l=new ListNode(a);
  else
  {
   ListNode *node=new ListNode(a);
   node->next=l->next;
   l->next=node;
  }
 }

 cur=l;
 while(cur->next)
  cur=cur->next;

 cur->next=l;

 cout << "The begin of the cyle : ";
 cout << s.detectCycle(l)->val << endl;

 return 0;
}
Tags: leetcode
Archives QR Code Tip
QR Code for this page
Tipping QR Code