[leetcode] linked-list-cycle

 

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

 

 

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

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

 

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

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

(위의 3,2,0,-4 같은 원소값들이 연결리스트 내에서 유일한 값인지는 모르겠다 -_-;ㅋㅋ)

 

 

두어 가지 방법을 사용할 수 있다.

 

 

 

 

1. HashSet 을 이용하는 방법

 

linked list를 순회하면서 원소들의 객체값을 저장해둔다.

객체값은 해당 노드만이 갖을 수 있는 값이기 때문에, 순회하면서 다시 마주친다면 cycle 이 있다고 생각할 수 있다.

 

/**
 * 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) {
        HashSet<Integer> set = new HashSet<>();
        boolean result = false;
        while(head!=null){
            if(head.next==null) {
                result = false;
                break;
            }
            else {
                if(set.contains(head.val)) {
                    result = true;
                    break;
                }
                set.add(head.val);
                head=head.next;
            }
        }
        return result;
    }
}

 

 

 

 

2. point 를 두 개 사용하는 방법

 

header 에서 출발하는 pointer slower와 pointer faster 두 개를 만들어본다.

slower가 한 번 움직일 때 faster 는 두 번 움직이게 한다.

(이 말인 즉 슨, slower 가 n번 움직이면 faster는 2n번 움직인다는 소리다.)

 

이런 방식으로 움직이게 되었을 때 slower 와 faster 가 똑같은 노드에서 만난다면(객체값으로 판별)

cycle 이 있다고 생각할 수 있다.

왜일까?

cycle 이 있는 연결리스트가 있다고 가정하자.

그리고 두 pointer 모두 cycle 내부에 처음으로 들어왔다고 하자(즉, slower 가 cycle의 첫번째 노드에 있는 상황)

slower와 faster 둘 다 cycle을 계속 순회한다.

slower 는 +1 만큼, faster 는 +2 만큼 순회한다.

순회를 하면 할수록, 차이가 1 만큼 벌어지기 때문에,

cycle 내부에서 무조건 slower 와 faster 는 만나게 된다.

이해가 안 된다면, 다르게 생각해보자.

slower는 그대로 있고, faster 만 +1 씩 움직인다고 생각해보자.

어쨌든 순회 할수록 차이는 1 만큼 벌어진다.

이 상태에서 faster 가 cycle을 한 바퀴 빙 돌아서, 멈춰있는 slower 에게 도달하게 된다.

즉, 무조건 slower 와 faster 는 cycle 내부에서 만나게 되어있다는 의미이다.

 

만약 두 pointer 중 하나라도 null 값이 된다면 cycle 이 없다는 의미가 된다.