Linked List Cycle

문제 : 

주어진 연결 리스트에 사이클(cycle)이 있는지 검사하는 함수를 만들면 된다.

아래와 같은 연결 리스트가 cycle 이 있는 연결리스트이다.

순회하는데 다음 값이 null 이면 무조건 cycle 이 없는 것이다.

또한 자기 자신을 가리키는 것도 cycle에 포함된다.

 

Example 1:

Linked List Cycle

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

 

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

 

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

제약 조건 :

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

 

Follow up :

Can you solve it using O(1) (i.e. constant) memory?

 

 

나의 코드 :

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
 
var hasCycle = function(head) {    
    
    // head가 null일 때 예외 처리    
    if(head  === null) return false;
    
    let one = head,
        two = head;   
    
    while(two && two.next){
          // one 노드 한 칸 이동
          one = one.next;
          
          // two 노드 두 칸 이동
          two = two.next.next;
          
          // one과 two의 값이 같을 때, 반환
        if(one === two) return true;
          }
    
    return false;    
};javascript

이해 안되는 부분 :

while(two && two.next) 조건.

two 나 two.next가 null이 들어오면 반복문이 끝나게 되는데, 

two는 순회를 한 번 이상 반복하며 one과 만나야 하는 것이 아닌가...?

처음에 while(one !== null)로 코드를 작성하다 해결이 안돼서 다른 분의 코드를 보고 해결했지만 이해가 안 간다...

내일 스터디에서 다시 한 번 이야기 해보는 게 좋겠다.

 

 

 

 

 

처음에는 원형 연결 리스트 메서드 구현 중 indexOf() 부분을 참고하여 코드를 작성하며 헤매다가

결국 구글링을 하고 다른 분들의 코드를 슬쩍 들여다 보았다.

거기서 '토끼와 거북이 알고리즘'을 배울 수 있었다.

 

토끼와 거북이 알고리즘은 쉽게 말해, 거북이는 한 칸씩, 토끼는 두 칸씩 앞으로 이동한다. 만약 순환구조가 있다면, 어떻게든 둘이 만나게 될 것이니, 이를 통해 순환여부를 확인할 수 있다는 알고리즘이다.

 

토끼와 거북이 알고리즘을 사용하면, 거북이가 일직선으로 직진하는 동안 순환여부를 알 수 있으므로 시간복잡도는 O(N)이며, 두 개의 포인터(토끼, 거북이)만을 사용하여 정답을 알 수 있으므로 공간복잡도는 사실상 거의 없다고 볼 수 있다. 

 

 

 

참고한 블로그 : https://dev-note-97.tistory.com/275?category=948582