https://www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle/problem
Cycle Detection | HackerRank
Given a pointer to the head of a linked list, determine whether the linked list loops back onto itself
www.hackerrank.com
연결리스트 내에서 사이클이 있는지 없는지 확인하는 문제이다.
head에서 시작하는 slow와 fast를 두 개 만든다.
slow는 한번 움직이고 fast는 두번 움직인다. (slow n번 움직이면 fast는 2n번 움직임)
이때 slow와 fast가 만나게 된다면 cycle이 발생하게 된다.
왜냐하면 순회를 하면 할수록 slow와 fast의 차이가 1만큼 벌어지게된다.
그렇게 되면 fast가 한바퀴를 돌아서 slow에 도달하게 된다.
slow가 정지했다고 가정하면 fast의 값만 1 증가하게 될것이고 fast가 cycle을 한 바퀴 돌아서 멈춰있는 slow에 도달하게 될 것이다.
따라서, 연결리스트 안에 cycle이 있다면 무조건 slow와 fast는 멈추게 된다.
코드는 연결리스트 선언부, 입력부, 출력부가 모두 작성되어 있어서 has_cylce 함수만 작성해주면 되었다.
slow와 fast 포인터를 선언해 주었고 이 둘은 head를 참조한다.
head는 연결리스트를 나타내며 head가 null이면 연결리스트는 존재하지 않는다.
fast가 null이 아니고 fast의 다음 노드가 null이 아닐동안 slow는 옆 노드로 이동하고 fast는 옆옆 노드로 이동한다.
만약 slow와 fast가 같으면 이것은 사이클이 있다는 뜻이므로 return 1을 한다.
head가 null이거나 fast가 null또는 fast->next가 null이면(이때는 while문에서 벗어나서 if에서 탈출하게 된다) return 0을 해준다.
