資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律學C++ 中的連結串列迴圈 II
考慮我們有一個連結串列，而我們必須檢查是否存在迴圈。為了在給定的連結串列中表示迴圈，我們將使用一個名為 pos 的整數指標。此 pos 表示連結串列中尾部連線到的位置。因此，如果 pos 為 -1，則連結串列中不存在迴圈。例如，連結串列為 [5, 3, 2, 0, -4, 7]，pos = 1。因此，存在一個迴圈，並且尾部連線到第二個節點。約束是，我們無法修改列表。
為解決這個問題，我們將按照以下步驟操作：
- slow := head 和 fast := head
- 當 slow、fast 和 fast 的下一個可用時，然後
- slow := slow 的下一個
- fast := (fast 的下一個) 的下一個
- 如果 slow = fast，則中斷
- 如果 fast 不為空或第一個的下一個不為空，則返回 null
- 如果 slow = fast，則
- slow := head
- 當 slow 與 fast 不同時
- slow := slow 的下一個和 fast := fast 的下一個
- 返回 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
更新於：04-5-2020
287 次瀏覽
Advertisement 廣告