[LeetCode] 141. Linked List Cycle

https://leetcode.com/problems/linked-list-cycle

개요

1. 어떤 링크드 리스트의 head 노드가 주어진다.
2. 이 링크드 리스트에 순환이 있는지 확인해라

문제 해결 아이디어

• 링크드 리스트의 다음 노드는 노드 별로 유일하게 가지고 있는 값이다.
  ➡️ 다음 노드는 일종의 pk이다.

🧐 다음 노드로 노드들을 구분하자.

의사 코드

1. head 노드를 가르키는 변수를 생성한다.
2. 노드를 다음 노드로 이동한다.
3. 노드가 set에 들어갈 수 없다. (조건)
   3-1. return true
4. 노드가 null 이다. (조건)
   4-1. return false

노드 = head 노드
while(노드 != null){
	노드 = 노드.next
    if(!set.add(노드)) return true
}
return false

결과

전체 코드 github 링크

다른 풀이

public boolean hasCycle(ListNode head) {

        ListNode s = head;
        ListNode f = head;
        while(f!=null && f.next!=null){
            s = s.next;
            f = f.next.next;
            if(s==f){
                return true;
            }
        }
        return false;
        
    }

거북이와 토끼 알고리즘을 이용해 링크드 리스트의 사이클을 확인할 수 있다.

거북이와 토끼 알고리즘
이 알고리즘에서는 거북이와 토끼라는 두 포인터가 데이터 구조를 순회한다. 거북이 포인터는 한 번에 한 단계씩 이동하고, 토끼 포인터는 거북이 포인터보다 두 배 빠르게 움직인다. 토끼 포인터는 거북이 포인터보다 두 배 빠른 속도로 움직이기 때문에 주기가 존재하면 특정 지점에서 거북이 포인터를 따라잡는다. 이 지점이 사이클의 교차점이다.

링크드 리스트와 거북이와 토끼 알고리즘이 밀접하게 연관된 만큼 꼭 기억해두자