확실히 알고가야 하는 자료구조, 알고리즘 개념 (7) : Linked List 루프 찾기

어떤 Linked List 안에 루프가 형성되어 있습니다.

 

이 루프의 시작 노드를 찾기 위해, 먼저 토끼와 거북이가 필요합니다.

 

토끼는 2 노드씩,

거북이는 1 노드씩 움직입니다.

 

여기서 토끼와 거북이는 절대 만나지 않는다고 걱정할 필요는 없습니다.

계속해서 토끼가 거북이를 뛰어 넘는다는 명제는 참이 될 수가 없는데,

미지수로 설정해 놓고 계산해보면 이 명제가 거짓임을 알 수 있습니다.

 

뛰어 넘었을 경우 토끼의 위치를 i로 설정한다면, 거북이의 위치는 i-1일 것입니다.

그렇지만 시간을 돌려 한 단계 전으로 이동하면, 토끼는 2 칸씩이니 i-2

거북이는 1 칸씩이니  (i-1)-1, 즉 i-2로 토끼와 거북이는 이미 만났다는 것이 됩니다.

 

그러니, 이 걱정은 접고 루프의 시작 노드를 찾는 방법으로 계속 진행해 보겠습니다.

 

루프의 들어가기 직전까지의 거리를 k라고 가정합니다.

거북이가 k만큼 왔을 때,

토끼의 위치는 2k일 것이고, 루프 안에서 k만큼 더 돌았습니다. (루프 전까지의 거리가 k이니까요)

그렇기에 토끼의 위치는 ' m = k % 루프의 길이 ' 입니다.

 

하지만 여기서 m는 결국 k와 같은데, 루프의 길이에 상관없이 몇 바퀴를 돌아도 위치는 똑같기 때문입니다.

(5개의 노드로 구성된 루프일 때, 7이나 12나 모두 같은 위치이기 때문입니다.)

(수학적으로 계산은 말도 안되지만, 루프를 돈다고 생각했을 때는 7 = 12 라고 볼 수 있으니 m = k가 됩니다.)

 

즉, 토끼는 시작점에서 m만큼 앞선 거리에 위치해 있을 것입니다.

 

이후, 거북이가 토끼를 만나러 루프 안으로 들어올 것이고,

토끼는 m만큼 앞서있습니다.

이는 토끼는 거북이보다 ' 루프의 길이 - m ' 만큼 뒤에 있다는 말과 같습니다.

이를 따라 잡으려면, 토끼는 {2 * (루프의 길이 - m)} 번 더 가야합니다.

 

거북이 입장에서는 이제 루프에 진입하고 ' 루프의 길이 - m '만큼 왔을 때 토끼에게 잡히게 됩니다.

다시 말해서 현재 위치는 루프 시작점에서 m만큼 뒤에 있는 곳입니다.

 

여기서 m만큼 앞으로 가면 시작점을 알 수 있다는 말과 같습니다.

 

이 때, 다시 거북이만 시작점에서 다시 m만큼 이동시키면 루프가 시작하는 위치에서 토끼와 거북이는 만나게 됩니다.

 

public class Test {
	public static void main (String[] args){
    	Node n1 = new Node(1);
        Node n2 = n1.addNext(2);
        Node n3 = n2.addNext(3);
        Node n4 = n3.addNext(4);
        Node n5 = n4.addNext(5);
        Node n6 = n5.addNext(6);
        Node n7 = n6.addNext(7);
        Node n8 = n7.addNext(8);
        n8.addNext(n4);
        
        Node n = findLoop(n1);
        
        if (n != null){
        	System.out.println(n.data);
        }
    }
    
    private static Node findLoop (Node head){
    	Node rabbit = head;
        Node turtle = head;
        
        while (rabbit != null && rabbit.next != null){ //루프가 없을 경우 토끼가 먼저 끝에 도착
        	turtle = turtle.next; //거북이는 한 칸씩
            rabbit = rabbit.next.next; //토끼는 두 칸씩
            if (rabbit == turtle){
            	break; //처음 만날 경우, 빠져나온다.
            }
        }
        
        if (rabbit == null || rabbit.next == null){ //루프가 아닐 경우, 함수를 끝낸다.
        	return null;
        }
        //루프일 경우, 거북이를 시작점에 보낸다.
        turtle = head;
        
        while (rabbit != turtle){ //둘이 만날 때까지 돌린다. //단 이때는 rabbit도 같은 속도로!
        	turtle = turtle.next;
           rabbit = rabbit.next;
        }
        
        return rabbit; //주소는 둘 중 아무거나 반환합니다. (만나는 지점이 바로 m)
        
    }
}