首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。