Xét một danh sách liên kết, ta phải kiểm tra xem có chu trình hay không. Để biểu diễn chu trình, ta dùng con trỏ nguyên pos. pos đại diện cho vị trí trong danh sách nơi đuôi được nối. Nếu pos = -1, không có chu trình. Ví dụ, danh sách [5, 3, 2, 0, -4, 7], pos = 1. Có chu trình, đuôi nối với nút thứ hai. Ràng buộc: không được sửa đổi danh sách.
Để giải quyết, ta làm theo các bước:
- slow := head và fast := head
- while slow, fast và next của fast tồn tại
- slow := next của slow
- fast := next của (next của fast)
- if slow = fast, thì break
- if fast rỗng hoặc next của fast rỗng, return null
- if slow = fast
- slow := head
- while slow khác fast
- slow := next của slow và fast := next của fast
- return slow
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h> using namespace std; class ListNode{ public: int val; ListNode *next; ListNode(int data){ val = data; next = NULL; } }; ListNode *make_list(vector<int> v){ ListNode *head = new ListNode(v[0]); for(int i = 1; i<v.size(); i++){ ListNode *ptr = head; while(ptr->next != NULL){ ptr = ptr->next; } ptr->next = new ListNode(v[i]); } return head; } ListNode *get_node(ListNode *head, int pos){ ListNode *ptr = head; if(pos != -1){ int p = 0; while(p < pos){ ptr = ptr->next; p++; } return ptr; } return NULL; } class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* slow = head; ListNode* fast = head; while(slow && fast && fast->next){ slow = slow->next; fast = fast->next->next; if(slow == fast)break; } if(!fast || !fast->next)return NULL; if(slow == fast){ slow = head; while(slow!=fast){ slow = slow->next; fast = fast->next; } } return slow; } }; main(){ Solution ob; vector<int> v = {5,3,2,0,-4,7}; ListNode *head = make_list(v); int pos = 1; ListNode *lastNode = get_node(head, v.size() - 1); lastNode->next = get_node(head, pos); cout << "Đuôi nối với nút có giá trị:" <<ob.detectCycle(head)->val; }Input
[5,3,2,0,-4,7] 1
Output
Đuôi nối với nút có giá trị:3