C++ 中的链表循环 II
c++server side programmingprogramming
假设我们有一个链表，我们需要检查其中是否存在循环。为了表示给定链表中的循环，我们将使用一个名为 pos 的整数指针。这个 pos 表示链表中 tail 所连接的位置。因此，如果 pos 为 -1，则表示链表中不存在循环。例如，链表为 [5, 3, 2, 0, -4, 7]，pos = 1。因此存在一个循环，并且 tail 连接到第二个节点。限制在于我们不能修改列表。
为了解决这个问题，我们将遵循以下步骤 −
- slow := head 且 fast := head
- 当 slow、fast 和 fast 的 next 可用时，则
- slow := slow 的 next
- fast := fast 的 next
- 如果 slow = fast，则 break
- 如果 fast 不为空或 first 的 next 不为空，则返回 null
- 如果 slow = fast，则
- slow := head
- 当 slow 不同于 fast 时
- slow := slow 的 next 且 fast := fast 的 next
- return slow
让我们看看下面的实现以便更好地理解 −
示例
#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
