CTCI | 뒤에서 k번째 원소

Cracking the Coding Interview

 

LinkedList에서 뒤에서 k번째 노드의 값을 찾는 알고리즘을 구현해라.

Linked List에서 뒤에서 k번째 노드를 찾는 알고리즘! 가장 간단한 방법은 무엇일까? 만약 10개의 노드가 있는데 k=3이라면? 8번째 노드가 뒤에서 세번째가 된다. 즉, 노드의 총 갯수를 구하고, 그것을 size 라고 했을 때, size - k 번 head에서 next한 노드의 값을 리턴하면 된다. 이 방법으로 하면, N개의 노드를 가진 LinkedList에서 O(N)의 Time Complexity로 계산할 수 있다.

 

코드로 한번 구현해보자.

int findKthNodeValue(Node head, int k){
	int count = 0;
    Node curr = head;
    while(curr != null){
    	count++;
        curr = curr.next;
    }
    
    // 만약, k가 총 갯수보다 적다면? 이럴 경우, head의 값을 리턴한다고 가정한다.
    if(count < k){
    	return head;
    }
    
    int index = count - k;
    curr = head;
    while(index > 0){
    	curr = curr.next;
        index--;
    }
    
    return curr.val;
}

 

사실 이 알고리즘은 O(N)으로 나타낼 수 있지만, 실제로는 2N, 즉 LinkedList를 거의 2번 도는 설계이다. 이것보다 조금더 효율적인 방법이 있을까? 있다! 바로 두개의 pointer를 이용하는 방법이다. faster pointer를 설정해서 k번을 먼저 가게한 다음, 두 포인터를 한칸씩 이동하게 해서, faster pointer가 null이 된다면, 그 자리에 있는 노드의 값을 리턴하면 된다! 

아래 코드로 위에 그린 로직을 표현해보자.

int findKthValue(Node head, int k){

	// Edge case로 head가 null이면 -1을 리턴한다.
	if(head == null){
    	return -1;
    }
    
    int index = k;
    Node slower = head;
    Node faster = head;
    while(index > 0){
    
    	// 만약 faster가 index가 0이 되기 전에 null에 도달했다면
        // 그것은 k보다 Linked List가 작다는 의미이다.
        // 임의로 -1를 리턴한다.
    	if(faster == null){
        	return -1;
        }
    	faster = faster.next;
        index--;
    }
    
    while(faster != null){
    	faster = faster.next;
        slower = slower.next;
    }
    
    return slower.val;
}

 

이렇게 하면, faster가 k만큼 가기는 했지만, 결과적으로는 N + k가 되기 때문에, 2N보다 훨씬 더 효율적인 알고리즘이 된다. Space는 두 알고리즘 모두 O(1)이라고 할 수 있다.