C++로 단일 연결 리스트의 뒤에서 K번째 노드 찾기

연결 리스트(Linked List)는 여러 개의 노드가 서로 연결되어 있는 선형 자료구조입니다. 각 노드는 데이터 필드와 다음 노드의 주소, 두 부분으로 구성됩니다. 이번 글에서는 주어진 단일 연결 리스트(singly linked list)에서 뒤에서 k번째 노드를 찾는 방법을 알아보겠습니다.

문제 예시

입력 −

1→2→3→4→7→8→9
K = 4

출력 −

뒤에서 4번째 위치의 노드 − 4

설명 − 주어진 단일 연결 리스트에서 뒤에서 4번째 노드는 '4'이므로, 결과값으로 '4'를 반환합니다.

문제 해결 접근 방식

우리에게는 노드들로 구성된 연결 리스트가 주어져 있습니다. 각 노드는 데이터와 다음 노드의 주소를 담고 있습니다. 뒤에서 k번째 노드를 찾기 위해 두 개의 포인터를 사용하며, 두 포인터 모두 처음에는 연결 리스트의 헤드(head)를 가리킵니다.

리스트를 순회할 때 한 포인터('fast')를 먼저 k칸 앞으로 이동시킨 뒤, fast 포인터가 리스트의 끝에 도달할 때까지 두 포인터를 함께 이동시키면 됩니다.

kthNodeFromTheEnd(node* head, int pos) 함수는 헤드 노드 포인터와 위치 값을 매개변수로 받아 뒤에서 해당 위치에 있는 노드를 반환합니다.
처음에 헤드를 가리키는 'slow'와 'fast' 두 포인터를 선언합니다.
연결 리스트를 순회하면서 fast 포인터를 k번 이동시킵니다.
이 시점에서 fast 포인터는 slow 포인터보다 정확히 k칸 앞서 있습니다. fast 포인터가 리스트의 끝(NULL)에 도달할 때까지 두 포인터를 동시에 이동시킵니다.
마지막으로 slow 포인터가 가리키는 노드의 값, 즉 뒤에서 k번째 노드의 값을 반환합니다.

C++ 코드 예제

#include<iostream>
using namespace std;
class node{
public:
    int data;
    node*next;
    node(int d){
        data=d;
        next=NULL;
    }
};
void insertAthead(node*&head,int d){
    node*n= new node(d);
    n->next= head;
    head=n;
}
void printList(node*head){
    while(head!=NULL){
        cout<<head->data<<"-->";
        head= head->next;
    }
}
void kthFromtheEnd(node*head, int k){
    node*slow= head;
    node*fast= head;
    for(int i=0;i<k;i++){
        fast= fast->next;
    }
    while(fast!=NULL){
        slow= slow->next;
        fast= fast->next;
    }
    cout<<"뒤에서 "<<k<<"번째 위치의 노드: "<<slow->data<<endl;
}
int main(){
    node*head= NULL;
    insertAthead(head,2);
    insertAthead(head,4);
    insertAthead(head,5);
    insertAthead(head,6);
    insertAthead(head,7);
    printList(head);
    cout<<endl;
    kthFromtheEnd(head,4);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

뒤에서 4번째 위치의 노드: 6

설명 − 위 코드에서 만들어진 연결 리스트는 7→6→5→4→2이며, k값은 '4'입니다. 따라서 뒤에서 4번째에 해당하는 노드는 '6'이므로, 최종적으로 '6'을 출력합니다. 이 방법은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 효율적으로 문제를 해결할 수 있습니다.