首页 > 代码库 > 011_hasCycle

011_hasCycle

 1 /* 2  * Author :SJQ 3  * 4  * Time   :2014-07-16-20.21 5  * 6  */ 7 #include <iostream> 8 #include <cstdio> 9 #include <cstdlib>10 using namespace std;11 12 struct ListNode {13 int val;14 ListNode *next;15 ListNode(int x) : val(x), next(NULL) {}16 };17 18 //利用快慢指针,链表有环,则快慢指针一定会相遇19 bool hasCycle(ListNode *head)20 {21     if (!head|| !head->next)22 return false;23 24     ListNode *fast, *slow;25     fast = slow = head;26     while(fast)27     {28         if (!fast->next)29 return false;30 31         fast = fast->next->next;32         slow = slow->next;33 34         if (fast == slow)35         {36             return true;37         }38     }39 40     return false;41 }42 43 int main()44 {45     freopen("input.txt", "r", stdin);46 int n;47 ListNode *head, *tail;48 49 while(cin >>n)50 {51 int num;52 for (int i = 0; i < n; ++i)53 {54 cin >> num;55 ListNode *temp = (ListNode*)malloc(sizeof(ListNode));56 temp->val = num;57 temp->next = NULL;58 59 if (i == 0)60 {61 head = temp;62 tail = temp;63 }64 else65 {66 tail->next = temp;67 tail = tail->next;68 }69 70 tail->next = NULL;71 }72 73         tail->next = head->next;        //手动每次把最后一个节点和第二个节点连起来74 bool flag = hasCycle(head);75         if (flag)76             cout << "has cycle!" << endl;77         else78             cout << "no cycle!" << endl;79 tail = head;80 for (int i = 0; i < n; ++i)81 82 {83    cout << tail->val << " ";84 tail =tail->next;85 }86 cout << endl;87 }88 89 return 0;90 91 }