?? detectloop.txt
字號:
How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list.
Discuss it!
/*
Start two pointers at the head of the list
Loop infinitely
If the fast pointer reaches a NULL pointer
Return that the list is NULL terminated
If the fast pointer moves onto or over the slow pointer
Return that there is a cycle
Advances the slow pointer one node
Advances the fast pointer two node
*/
#include <stdio.h>
#include <stdlib.h>
struct linkedList{
int element;
struct linkedList* next;
};
typedef struct linkedList* List;
/* Takes a pointer to the head of a linked list and determines
if the list ends in a cycle or is NULL terminated
*/
int DetermineTermination(List *head)
{
List *fast, *slow;
fast = slow = head;
while(1)
{
if(!fast || !fast->next)
return 0;
else if(fast == slow || fast ->next == slow)
return 1; // Loop detected
else{
slow = slow->next;
fast = fast->next->next;
}
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -