#141 Linked List Cycle

문제링크 - https://leetcode.com/problems/linked-list-cycle/?envType=study-plan-v2&envId=top-interview-150

문제 조건

• The number of the nodes in the list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• pos는 -1 또는 링크드리스트의 유효한 위치이다.
  ListNode가 주어졌을 때 순환이 있으면 true 없으면 false를 반환.

문제 해결

문제 해결 로직

해당 문제는 토끼와 거북이 방법을 사용하면 쉽게 풀 수 있다.
두 node의 속도를 다르게 다음 노드를 참조하게 되었을 때, 순환하지 않는다면 먼저 간 노드가 끝(null)에 도달하지만, 만약 순환한다면 늦게 참조하는 노드와 빨리 참조하는 노드가 만나게 될 것이다.

데이터 입력

문제에서 입력이 들어오는 데이터는 ListNode head이다. 해당 노드를 시작으로 두 노드를 움직여 위치를 비교할 수 있다.

• fast
  빠르게 이동할 node
• slow
  천천히 이동할 node

  ListNode fast = head;
  ListNode slow = head;

node 위치 변경하기

빠르게 옮기던 node가 끝에 도달하여 다음 노드가 없을 떄 까지 slow와 fast 노드를 이동시킨다. 단, fast는 두칸씩 빠르게 이동한다.
만약 순환한다면 반복문을 꼐속 돌아 언젠간 slow와 fast의 위치가 같아진다.

while(fast!=null && fast.next!=null){
          slow = slow.next;
          fast = fast.next.next;
          if(slow == fast){
            return true;
          }
        }
        return false;
    }

코드 작성

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while(fast!=null && fast.next!=null){
          slow = slow.next;
          fast = fast.next.next;
          if(slow == fast){
            return true;
          }
        }
        return false;
    }
}

복잡도 계산

• 시간 복잡도

  • fast 포인터는 한 번의 루프에서 두 칸씩 이동하고, slow 포인터는 한 칸씩 이동한다.
  • 순환의 길이를 L이라고 할 때, fast 포인터는 L/2 번 정도 이동하면 순환 내에서 slow 포인터와 겹치게 된다.
  • 따라서 최악의 경우에도 fast 포인터와 slow 포인터가 순환 내에서 만나는데 O(L)의 시간이 걸린다. 그 외의 경우에는 O(n) 시간에 탐지할 수 있다.
  • 이 알고리즘은 시간 복잡도는 O(L) 또는 O(n).

• 공간 복잡도

  • 변수는 상수형 데이터만 가지고 있기 떄문에 O(1)의 공간 복잡도를 가진다.

회고

• ListNode의 전체 구조를 확인할 수 없기 때문에 순환을 다음과 같은 방법으로 확인했다.