연결 리스트가 있다고 가정하고 순환이 있는지 없는지 확인해야 합니다. 주어진 연결 목록에서 주기를 나타내기 위해 pos라는 정수 포인터 하나를 사용합니다. 이 위치는 연결 리스트에서 꼬리가 연결된 위치를 나타냅니다. 따라서 pos가 -1이면 연결 목록에 사이클이 없습니다. 예를 들어 연결 리스트는 [5, 3, 2, 0, -4, 7]과 같으며, pos =1입니다. 따라서 주기가 있고 두 번째 노드에 tail이 연결됩니다. 제약 조건은 목록을 수정할 수 없다는 것입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 느림 :=선두, 빠름 :=선두
- 느림, 빠름, 빠름 다음을 사용할 수 있는 동안
- slow :=다음으로 느림
- 빠른 :=다음 중 (빠른 것의 다음)
- 느림 =빠르면 중단
- fast가 비어 있지 않거나 첫 번째의 다음이 비어 있지 않으면 null을 반환합니다.
- 느림 =빠름이면
- 느림 :=머리
- 느림은 빠름과 같지 않음
- 느림 :=느림과 빠름의 다음 :=빠름의 다음
- 느린 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#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 << "Tail is connected to the node with value:" <<ob.detectCycle(head)->val;
} 입력
[5,3,2,0,-4,7] 1
출력
Tail is connected to the node with value:3