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 else
65 {
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         else
78             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 }