연결 리스트 주기

리트코드 문제: Linked List Cycle

목적:

연결된 목록의 헤드인 head가 주어지면 연결된 목록에 순환이 있는지 확인합니다.

다음 포인터를 계속 따라가면 다시 도달할 수 있는 노드가 목록에 있으면 연결 목록에 순환이 있습니다. 내부적으로 pos는 tail의 다음 포인터가 연결된 노드의 인덱스를 나타내는 데 사용됩니다. pos는 매개변수로 전달되지 않습니다.

연결된 목록에 순환이 있으면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.


패턴: 두 포인터 기술


접근하다:

극단적인 경우: 입력이 null이면 목록이 비어 있으므로 순환이 존재하지 않습니다.

헤드에서 시작하여 두 개의 포인터를 만듭니다. 한 포인터는 느린 속도로 움직이고 다른 포인터는 두 배의 속도로 움직입니다.

더 느린 포인터가 더 빠른 포인터를 따라잡는 경우 사이클이 있기 때문에 true를 반환합니다.

더 빠른 포인터가 null에 도달하면 주기가 없기 때문에 false를 반환합니다.

빅오 표기법:

시간 복잡도: O(n)
각 요소에 대해 n번 반복합니다.

공간 복잡도: O(1)
우리는 저장을 위해 추가 데이터 구조를 사용하지 않습니다.

암호:

public class Solution {
    public boolean hasCycle(ListNode head) {

        if(head == null){
            return false;
        }

        ListNode slow = head; 
        ListNode fast = head;

        while(fast != null && fast.next != null){

            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}