[LeetCode 142] 142. Linked List Cycle II(feat. 플로이드의 순환찾기 알고리즘)

영어로 문제를 푼다는것은 자신감을 떨어뜨리고 내가 맞게 해석했는지 의문이 든다... 리트코드에 적응하면 조금은 괜찮아질거라 믿으며 글을쓴다.

이 문제는 모르면 못푸는 문제이다. 몰라서 못풀었고 토끼와 거북이 알고리즘이란 것을 알게되어 배움의 의미로 글을 작성한다.

 

토끼와 거북이 알고리즘이란

토끼와 거북이 알고리즘은 LinkedList에서 순환 루프 여부를 확인하고 순환 루프의 시작 노드를 알아내는 데 사용되는 알고리즘이다.

 

자세한 증명 과정은 다음과 같다.

 

---

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        ListNode* rabbit = head;
        ListNode* tortoise = head;

        while (rabbit) {

            if(rabbit->next == NULL)
            {
                rabbit = rabbit->next;
                break;   
            }
            rabbit = rabbit->next->next;

            tortoise = tortoise->next;

            if(rabbit == tortoise) break;
        }
        if(rabbit == NULL) return NULL;

        tortoise = head;

        while (1) {
            if(rabbit == tortoise) return rabbit;
            rabbit = rabbit->next;
            tortoise = tortoise->next;


        }

        return NULL;
    }
};

---