단일 연결 목록에서 루프 찾기
단일 연결 목록에 루프가 있는지 여부를 어떻게 감지 할 수 있습니까 ?? 루프가있는 경우 루프의 시작 지점, 즉 루프가 시작된 노드를 찾는 방법.
목록을 통해 두 개의 포인터를 실행하여이를 감지 할 수 있습니다 .이 프로세스는 같은 이름의 우화 뒤에 거북이와 토끼 알고리즘으로 알려져 있습니다.
먼저 목록이 비어 있는지 확인하십시오 ( headis null). 그렇다면 루프가 불가능하므로 지금 중지하십시오.
그렇지 않으면 tortoise첫 번째 노드에서 첫 번째 포인터 를 시작 하고 두 번째 노드에서 두 head번째 포인터 hare를 시작합니다 head.next.
그런 다음 hareis null(하나의 요소 목록에서 이미 참일 수 있음) 까지 계속 반복하여 각 반복에서 tortoise1과 hare2 씩 진행 합니다 . 토끼는 먼저 시작하여 더 빨리 달릴 수 있기 때문에 먼저 끝까지 (끝 이 있다면) 보장됩니다 .
끝이 없으면 (즉, 루프가있는 경우) 결국 동일한 노드를 가리키고 루프 내 어딘가 에서 노드를 찾았다는 것을 알고 중지 할 수 있습니다 .
에서 시작하는 다음 루프를 고려하십시오 3.
head -> 1 -> 2 -> 3 -> 4 -> 5
^ |
| V
8 <- 7 <- 6
tortoise1과 hare2 에서 시작 하여 다음 값을 취합니다.
(tortoise,hare) = (1,2) (2,4) (3,6) (4,8) (5,4) (6,6)
그들은에서 동일하게하기 때문에 (6,6), 이후 hare한다 항상 초과 할 tortoise비 루핑 목록에, 당신이 루프를 발견 한 것을 의미한다.
의사 코드는 다음과 같이됩니다.
def hasLoop (head):
return false if head = null # Empty list has no loop.
tortoise = head # tortoise initially first element.
hare = tortoise.next # Set hare to second element.
while hare != null: # Go until hare reaches end.
return false if hare.next null # Check enough left for hare move.
hare = hare.next.next # Move hare forward two.
tortoise = tortoise.next # Move tortoise forward one.
return true if hare = tortoise # Same means loop found.
endwhile
return false # Loop exit means no loop.
enddef
이 알고리즘의 시간 복잡성은 O(n)(거북이와 토끼에 의해) 방문한 노드의 수가 노드의 수에 비례하기 때문입니다.
루프 내의 노드를 알게되면 루프 O(n)의 시작 을 찾는 보장 된 방법 도 있습니다 .
루프의 어딘가에서 요소를 찾았지만 루프의 시작 위치가 확실하지 않은 경우 원래 위치로 돌아 갑시다.
head -> 1 -> 2 -> 3 -> 4 -> 5
^ |
| V
8 <- 7 <- 6
\
x (where hare and tortoise met).
따라야 할 프로세스는 다음과 같습니다.
- 진행
hare하고로 설정size합니다1. - 그런 다음
hare과tortoise가 다른 한 계속 진행하여 매번hare증가size합니다. 이것은 결국 루프의 크기를 제공합니다.이 경우 6입니다. - 경우이 시점에서,
size이다1, 그 수단을you must *already* be at the start of the loop (in a loop of size one, there is only one possible node that can *be* in the loop so it *must* be the first in that loop). In this case, you simply return시작으로 hare`, 아래의 나머지 단계를 건너 뜁니다. - 그렇지 않으면
hare및 둘 다 목록tortoise의 첫 번째 요소로 설정하고hare정확히size시간 (7이 경우에는로)으로 진행합니다. 이것은 루프의 크기 가 정확히 다른 두 개의 포인터를 제공 합니다. - 그런 다음
hare과tortoise가 다른 한 두 마리를 함께 전진시킵니다 (토끼가 거북이와 같은 속도로 더 안정된 속도로 달리면서-첫 달리기부터 피곤한 것 같습니다). 그들이 정확히 남아 있기 때문에size항상 서로 떨어져 요소를tortoise것 도달 에 루프의 시작을 정확히 같은 시간hare반환 루프의 시작.
다음 연습을 통해 확인할 수 있습니다.
size tortoise hare comment
---- -------- ---- -------
6 1 1 initial state
7 advance hare by six
2 8 1/7 different, so advance both together
3 3 2/8 different, so advance both together
3/3 same, so exit loop
따라서 3루프의 시작점이며 두 작업 (루프 감지 및 루프 시작 검색)이 모두 O(n)순차적으로 수행되고 수행 되기 때문에 함께 취한 모든 것이 O(n).
이것이 작동한다는보다 공식적인 증거를 원한다면 다음 리소스를 검토 할 수 있습니다.
- 자매 사이트에 대한 질문 ;
- 위키 백과 사이클 탐지 페이지; 또는
- 2016 년 4 월 17 일 Peter Gammie의 "거북이와 토끼 알고리즘"
방법에 대한 지원 (공식적 증명이 아님) 만한다면 다음 Python 3 프로그램을 실행하여 많은 크기 (사이클의 요소 수)와 도입부 (전의 요소)에 대한 작업 가능성을 평가할 수 있습니다. 사이클 시작).
항상 두 포인터가 만나는 지점을 찾습니다.
def nextp(p, ld, sz):
if p == ld + sz:
return ld
return p + 1
for size in range(1,1001):
for lead in range(1001):
p1 = 0
p2 = 0
while True:
p1 = nextp(p1, lead, size)
p2 = nextp(nextp(p2, lead, size), lead, size)
if p1 == p2:
print("sz = %d, ld = %d, found = %d" % (size, lead, p1))
break
선택된 답은 사이클의 시작 노드를 찾기위한 O (n * n) 솔루션을 제공합니다. 다음은 O (n) 솔루션입니다.
주기에서 느린 A와 빠른 B가 만나는 것을 발견하면 그중 하나를 고정시키고 다른 하나는주기의 둘레를 결정하기 위해 매번 한 단계 씩 계속 진행합니다 (예 : P).
그런 다음 헤드에 노드를 놓고 P 단계로 이동하고 다른 노드를 헤드에 놓습니다. 우리는이 두 노드를 매번 한 단계 씩 전진시킵니다. 처음 만날 때, 이것이주기의 시작점입니다.
해시 맵을 사용하여 링크 목록에 루프가 있는지 여부를 찾을 수 있습니다. 아래 함수는 해시 맵을 사용하여 링크 목록에 루프가 있는지 여부를 알아냅니다
static bool isListHaveALoopUsingHashMap(Link *headLink) {
map<Link*, int> tempMap;
Link * temp;
temp = headLink;
while (temp->next != NULL) {
if (tempMap.find(temp) == tempMap.end()) {
tempMap[temp] = 1;
} else {
return 0;
}
temp = temp->next;
}
return 1;
}
시간 복잡도가 O (n) Hash Map에 O (n) 공간 복잡도가 필요하기 때문에 두 포인터 방법이 가장 좋은 방법입니다.
나는 Narasimha Karamanchi의 Data structure book에서이 답변을 읽었습니다.
우리는 거북이와 토끼 알고리즘 으로 알려진 플로이드주기 찾기 알고리즘을 사용할 수 있습니다 . 여기에는 두 개의 포인터가 사용됩니다. 하나 (예 )는 단일 노드에 의해 전진되고 다른 하나 (예 :)는 두 노드에 의해 전진됩니다. 단일 연결 목록에 루프가 있으면 둘 다 어느 시점에서 확실히 만날 것입니다.slowPtrfastPtr
struct Node{
int data;
struct Node *next;
}
// program to find the begin of the loop
int detectLoopandFindBegin(struct Node *head){
struct Node *slowPtr = head, *fastPtr = head;
int loopExists = 0;
// this while loop will find if there exists a loop or not.
while(slowPtr && fastPtr && fastPtr->next){
slowPtr = slowPtr->next;
fastPtr = fastPtr->next->next;
if(slowPtr == fastPtr)
loopExists = 1;
break;
}
루프가 있으면 포인터 중 하나를 헤드로 가리키고 이제 두 포인터를 단일 노드로 진행합니다. 그들이 만날 노드는 단일 연결 목록에서 루프 의 시작 노드가됩니다.
if(loopExists){
slowPtr = head;
while(slowPtr != fastPtr){
fastPtr = fastPtr->next;
slowPtr = slowPtr->next;
}
return slowPtr;
}
return NULL;
}
대부분의 경우 이전 답변은 모두 정확하지만 여기에는 시각적 및 코드가있는 논리의 단순화 된 버전이 있습니다 (Python 3.7 용)
다른 사람들이 설명했듯이 논리는 매우 간단합니다. Tortoise / slow 및 Hare / fast를 만들 것입니다. 다른 속도로 두 개의 포인터를 움직이면 결국 빠른 속도가 느린 속도를 만나게됩니다 !! 이것은 또한 압정 원형 필드에있는 두 명의 주자라고 생각할 수 있습니다. 빠른 주자가 계속 원을 그리면 느린 주자를 만나거나 통과합니다.
그래서 우리는 반복 할 때마다 속도가 1 인 거북이 / 느린 포인터를 움직일 것입니다. 토끼 / 빠른 포인터를 계속 증가 시키거나 2의 속도로 움직일 것입니다. 그들이 만나면 우리는주기가 있다는 것을 압니다. 이것은 Floyd의주기 찾기 알고리즘 이라고도 합니다. 
이 작업을 수행하는 Python 코드는 다음과 같습니다 (has_cycle 메서드가 주요 부분입니다).
#!/usr/bin/env python3
class Node:
def __init__(self, data = None):
self.data = data
self.next = None
def strnode (self):
print(self.data)
class LinkedList:
def __init__(self):
self.numnodes = 0
self.head = None
def insertLast(self, data):
newnode = Node(data)
newnode.next = None
if self.head == None:
self.head = newnode
return
lnode = self.head
while lnode.next != None :
lnode = lnode.next
lnode.next = newnode # new node is now the last node
self.numnodes += 1
def has_cycle(self):
slow, fast = self.head ,self.head
while fast != None:
if fast.next != None:
fast = fast.next.next
else:
return False
slow = slow.next
if slow == fast:
print("--slow",slow.data, "fast",fast.data)
return True
return False
linkedList = LinkedList()
linkedList.insertLast("1")
linkedList.insertLast("2")
linkedList.insertLast("3")
# Create a loop for testing
linkedList.head.next.next.next = linkedList.head;
#let's check and see !
print(linkedList.has_cycle())
다음 코드는 SLL에 루프가 있는지 여부를 확인하고 루프가있는 경우 시작 노드를 반환합니다.
int find_loop(Node *head){
Node * slow = head;
Node * fast = head;
Node * ptr1;
Node * ptr2;
int k =1, loop_found =0, i;
if(!head) return -1;
while(slow && fast && fast->next){
slow = slow->next;
/*Moving fast pointer two steps at a time */
fast = fast->next->next;
if(slow == fast){
loop_found = 1;
break;
}
}
if(loop_found){
/* We have detected a loop */
/*Let's count the number of nodes in this loop node */
ptr1 = fast;
while(ptr1 && ptr1->next != slow){
ptr1 = ptr1->next;
k++;
}
/* Now move the other pointer by K nodes */
ptr2 = head;
ptr1 = head;
for(i=0; i<k; i++){
ptr2 = ptr2->next;
}
/* Now if we move ptr1 and ptr2 with same speed they will meet at start of loop */
while(ptr1 != ptr2){
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return ptr1->data;
}
boolean hasLoop(Node *head)
{
Node *current = head;
Node *check = null;
int firstPtr = 0;
int secondPtr = 2;
do {
if (check == current) return true;
if (firstPtr >= secondPtr){
check = current;
firstPtr = 0;
secondPtr= 2*secondPtr;
}
firstPtr ++;
} while (current = current->next());
return false;
}
또 다른 O (n) 솔루션.
선택한 답변을 보았을 때 몇 가지 예를 시도한 결과 다음과 같은 결과를
얻었습니다 .If (A1, B1), (A2, B2) ... (AN, BN)이 포인터 A와 B의 순회이며
A 단계 1 요소 B 단계 2 요소, Ai 및 Bj는 A와 B가 횡단하는 노드이며 AN = BN입니다.
그런 다음 루프가 시작되는 노드는 Ak입니다. 여기서 k = floor (N / 2)입니다.
ok-어제 인터뷰에서이 문제를 만났습니다-사용 가능한 참고 자료가 없었고 매우 다른 답변을 내놓았습니다 (물론 집으로 운전하는 동안 ...) 연결된 목록이 malloc 논리를 사용하여 할당 된 정상적이기 때문에 (항상 인정하는 것은 아닙니다) 그러면 우리는 할당의 세분성이 알려져 있음을 압니다. 대부분의 시스템에서 이것은 8 바이트입니다. 즉, 하위 3 비트는 항상 0입니다. 고려하십시오-연결 목록을 클래스에 배치하여 액세스를 제어하고 다음 주소에 0x0E 마스크를 사용하면 하위 3 비트를 사용하여 브레이크 크럼을 저장할 수 있습니다. 따라서 마지막 브레드 크럼을 저장할 메서드를 작성할 수 있습니다. -1 또는 2라고 말하고 번갈아 가며 말하십시오. 루프를 확인하는 방법은 다음 방법을 사용하여 각 노드를 단계별로 진행하고 다음 주소에 현재 이동 경로가 포함되어 있는지 확인할 수 있습니다. 루프가있는 경우 루프가없는 경우 하위 3 비트를 마스킹합니다. 현재 이동 경로를 추가합니다. 이동 경로 검사 알고리즘은 한 번에 두 개를 실행할 수 없기 때문에 단일 스레드 여야하지만 다른 스레드가 목록 비동기에 액세스 할 수 있도록 허용합니다. 노드 추가 / 삭제에 대한 일반적인주의 사항이 있습니다. 어떻게 생각해? 다른 사람들이 이것이 타당한 해결책이라고 생각한다면 샘플 클래스를 작성할 수 있습니다. 가끔 신선한 접근 방식이 좋다고 생각하고 항상 요점을 놓쳤다는 말을 듣고 싶어합니다. 감사합니다 All Mark 이동 경로 검사 알고리즘은 한 번에 두 개를 실행할 수 없기 때문에 단일 스레드 여야하지만 다른 스레드가 목록 비동기에 액세스 할 수 있도록 허용합니다. 노드 추가 / 삭제에 대한 일반적인 경고가 있습니다. 어떻게 생각해? 다른 사람들이 이것이 타당한 해결책이라고 생각한다면 샘플 클래스를 작성할 수 있습니다. 가끔 신선한 접근 방식이 좋다고 생각하고 항상 요점을 놓쳤다는 말을 듣고 싶어합니다. 감사합니다 All Mark 이동 경로 검사 알고리즘은 한 번에 두 개를 실행할 수 없기 때문에 단일 스레드 여야하지만 다른 스레드가 목록 비동기에 액세스 할 수 있도록 허용합니다. 노드 추가 / 삭제에 대한 일반적인주의 사항이 있습니다. 어떻게 생각해? 다른 사람들이 이것이 타당한 해결책이라고 생각한다면 샘플 클래스를 작성할 수 있습니다. 가끔 신선한 접근 방식이 좋다고 생각하고 항상 요점을 놓쳤다는 말을 듣고 싶어합니다. 감사합니다 All Mark
또 다른 해결책
루프 감지 :
- 목록을 만들다
- 연결 목록을 반복하고 목록에 노드를 계속 추가하십시오.
- 노드가 이미 목록에있는 경우 루프가 있습니다.
루프 제거 :
- 위의 2 단계에서 연결 목록을 반복하면서 이전 노드도 추적합니다.
3 단계에서 루프를 감지하면 이전 노드의 다음 값을 NULL로 설정합니다.
#암호
def detect_remove_loop (head)
cur_node = head node_list = [] while cur_node.next is not None: prev_node = cur_node cur_node = cur_node.next if cur_node not in node_list: node_list.append(cur_node) else: print('Loop Detected') prev_node.next = None return print('No Loop detected')
첫째, 노드 생성
struct Node {
int data;
struct Node* next;
};
헤드 포인터를 전역 적으로 초기화
Struct Node* head = NULL;
연결된 목록에 일부 데이터 삽입
void insert(int newdata){
Node* newNode = new Node();
newNode->data = newdata;
newNode->next = head;
head = newNode;
}
detectLoop () 함수 만들기
void detectLoop(){
if (head == NULL || head->next == NULL){
cout<< "\nNo Lopp Found in Linked List";
}
else{
Node* slow = head;
Node* fast = head->next;
while((fast && fast->next) && fast != NULL){
if(fast == slow){
cout<<"Loop Found";
break;
}
fast = fast->next->next;
slow = slow->next;
}
if(fast->next == NULL){
cout<<"Not Found";
}
}
}
main ()에서 함수 호출
int main()
{
insert(4);
insert(3);
insert(2);
insert(1);
//Created a Loop for Testing, Comment the next line to check the unloop linkedlist
head->next->next->next->next = head->next;
detectLoop();
//If you uncomment the display function and make a loop in linked list and then run the code you will find infinite loop
//display();
}
bool FindLoop(struct node *head)
{
struct node *current1,*current2;
current1=head;
current2=head;
while(current1!=NULL && current2!= NULL && current2->next!= NULL)
{
current1=current1->next;
current2=current2->next->next;
if(current1==current2)
{
return true;
}
}
return false;
}
아주 다른 방법 :-연결 목록을 반대로합니다. 반전하는 동안 다시 머리에 도달하면 목록에 루프가 있고 NULL을 얻으면 루프가 없습니다. 총 시간 복잡도는 O (n)입니다.
참고 URL : https://stackoverflow.com/questions/10275587/finding-loop-in-a-singly-linked-list
'Program Tip' 카테고리의 다른 글
| JSON 개체 목록을 통해 반복 (0) | 2020.12.06 |
|---|---|
| 에뮬레이터에서 확대 / 축소 할 수 없음 (0) | 2020.12.06 |
| FTP를 통한 Python 스크립트 업로드 파일 (0) | 2020.12.06 |
| Xcode 6 Swift 코드 완성이 작동하지 않음 (0) | 2020.12.06 |
| 부모 외부로 이동하면 Android보기가 사라짐 (0) | 2020.12.06 |