C++로 연결 리스트의 중간에서 헤드 방향으로 k번째 노드 찾기

이 문제에서는 연결 리스트(Linked List)와 숫자 k가 주어지며, 연결 리스트의 중간 노드에서 헤드(Head) 방향으로 k번째 노드를 찾는 것이 우리의 과제입니다.

문제 이해를 위한 예시

입력: 연결 리스트 : 4 -> 2 -> 7 -> 1 -> 9 -> 12 -> 8 -> 10 -> 5, k = 2

출력: 7

설명:

중간 노드의 값은 9입니다.

중간 노드에서 헤드 방향으로 두 번째에 위치한 노드의 값은 7입니다.

해결 접근 방법

연결 리스트의 중간에서 시작 부분 방향으로 k번째 요소를 찾아야 합니다. 이를 위해서는 먼저 연결 리스트를 처음부터 끝까지 순회하여 리스트의 전체 크기(n)를 구해야 합니다.

리스트의 크기를 n이라고 할 때, 중간에서 시작 방향으로 k번째 요소는 처음부터 (n/2 + 1 - k)번째 요소와 같습니다. 따라서 이 위치의 노드 값을 반환하면 됩니다.

만약 계산된 위치가 0 이하라면, 해당하는 노드가 존재하지 않으므로 -1을 반환하여 유효하지 않음을 나타냅니다.

해결 방법을 구현한 프로그램

예제 코드

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

void pushNode(struct Node** head_ref, int new_data)
{
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int findKmiddleNode(struct Node* head_ref, int k) {
    
    int n = 0;
    struct Node* counter = head_ref;
    while (counter != NULL) {
        n++;
        counter = counter->next;
    }
    int reqNode = ((n / 2 + 1) - k);

    if (reqNode <= 0)
        return -1;
        
    struct Node* current = head_ref;
    int count = 1;
    while (current != NULL) {
        if (count == reqNode)
            return (current->data);
        count++;
        current = current->next;
    }
}

int main()
{

    struct Node* head = NULL;
    int k = 2;
    pushNode(&head, 5);
    pushNode(&head, 10);
    pushNode(&head, 8);
    pushNode(&head, 12);
    pushNode(&head, 9);
    pushNode(&head, 1);
    pushNode(&head, 7);  
    pushNode(&head, 2);
    pushNode(&head, 4);

    cout<<k<<"번째 요소(헤드 방향 기준)는 "<<findKmiddleNode(head, k);

    return 0;
}

실행 결과

2번째 요소(헤드 방향 기준)는 7

코드 설명

위 코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

1단계: findKmiddleNode 함수는 먼저 counter 포인터를 사용해 연결 리스트 전체를 순회하며 노드의 총 개수 n을 계산합니다.

2단계: 목표 노드의 위치 reqNode를 공식 (n/2 + 1) - k로 계산합니다. 예제에서 n = 9, k = 2이므로 reqNode = (9/2 + 1) - 2 = 4가 됩니다.

3단계: 계산된 위치가 0 이하인 경우 유효한 노드가 없으므로 -1을 반환합니다.

4단계: 다시 리스트를 처음부터 순회하며 count가 reqNode와 일치하는 노드의 데이터 값을 반환합니다.

이 알고리즘의 시간 복잡도는 리스트를 두 번 순회하므로 O(n)이며, 추가적인 공간 사용 없이 해결할 수 있어 공간 복잡도는 O(1)입니다.