[leetcode/C]리트코드 - 141번

 

문제 링크 : https://leetcode.com/problems/linked-list-cycle/

문제

연결리스트가 순환하는지에 대한 여부를 판별하는 문제

입력

head = [3,2,0,-4] 와 같은 연결리스트의 head를 함수의 매개변수로 준다.

출력

순환하면 true, 순환하지 않으면 false를 리턴

---

접근방식

 

floyd's tortoise and hare 이라는 알고리즘을 이용해서 해결했다.
한글로 번역하면, 토끼와 거북이라는 알고리즘인데, 2개의 포인터의 이동하는 속도가 다른 걸 이용해서 연결리스트의 순환 여부를 판단한다. 재밌는 알고리즘이다.

 

코드

bool hasCycle(struct ListNode *head) {
    struct ListNode* turtle;
    struct ListNode* rabbit;
    turtle = head;
    rabbit = head;
    
    while(turtle !=NULL && rabbit != NULL){
        
        if(rabbit->next == NULL) return false;
        rabbit = rabbit->next->next;
        turtle = turtle->next;
        if(turtle == rabbit) return true;
    }
    return false;
}

 

토끼와 거북이라는 이름을 갖는 2개의 포인터를 선언한 후에, 같은 지점에서 연결리스트를 순회한다.
토끼는 연결리스트를 2칸씩 움직이고, 거북이는 1칸씩 이동한다. 만약, 토끼나 거북이의 다음 노드가 NULL 이라면, 이 연결리스트는 순환하지 않으므로 false를 반환. 순환한다면, 둘의 순회 속도가 다르기 때문에 한 지점에서 만날 것이다.

토끼와 거북이가 같은 곳에서 만나면 true를 반환한다.

 

 

다른 문제의 코드 : https://github.com/DaeeYong/Algorithm-Solution-

DaeeYong/Algorithm-Solution-