확실히 알고가야 하는 자료구조, 알고리즘 개념 (3) : 단방향 Linked List의 끝에서 k 번째 노드 찾기

방법 1

 

뒤에서 k 번째는 앞에서 n - k + 1 번째 노드

---

방법 2

 

재귀 호출

: 조건이 만족될 때까지 계속해서 호출하는 방법

>> 끝까지 들어갔다가 k 번을 세면서 나오면 됩니다.

private static void KthToLast(Node n, int k){
	if(n == null){
    	return 0;
    }
    int count = KthToLast(n.next, k) + 1;
    if (count == k){
    	System.out.println(k + "th to last node is" + n.data);
    }
    return count;
}

값이 아닌 노드를 찾으라는 문제였기에, 다른 것을 출력해야 합니다.

 

C++에서는 PathByReference라는 기능(값이 아닌 주소를 전달)을 이용해 노드를 출력할 수 있는데, Java에선 그럴 수 없습니다.

 

그렇기에, 객체나 배열 등은 Stack에 Pointer만 저장을 하는 특성을 이용해서 이를 해결합니다.

 

class Reference {
	public int count. 0; //여기서 . 0 의 의미를 모르겠습니다.
}

private static Node KthToLast(Node n, int k, Reference r){ //이제 count는 Reference에 저장하니, Data Type을 Node로 변경합니다.
	if (n == null){
    	return null;
    }
   	
    Node found = KthToLast(n, k, r);
    r.count++;
    if (r.count == k){
    	return n;
    }
    return found;
}
    

공간: O(N)

시간: O(2N) > 그냥 O(N)으로 표기

---

방법 3.

 

포인터

 

포인터 2개가 노드를 돌도록 만듭니다.

그 포인터끼리의 차이를 k로 설정해두고, 이동시킵니다.

앞선 포인터가 null을 만났을 때 뒤 포인터의 노드가 뒤에서 k 번째 노드입니다.

private static Node KthToLast(Node first, int k){
	Node p1 = first;
    Node p2 = first;
    
    for (int i = 0; i < k; i++){
    	if (p1 == null) return null;
        p1 = p1.next;
    }
    
    while (p1 != null) {
    	p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}

시간 O(N)

공간 O(1)