C++ 연결 리스트에서 오른쪽 최댓값 노드를 가리키는 임의 포인터 설정 방법

문제 소개

이 문제에서는 데이터(data), 다음 노드를 가리키는 링크 포인터(next), 그리고 임의 포인터(arbitrary pointer)를 함께 가지는 연결 리스트가 주어집니다. 우리가 해야 할 작업은 각 노드의 임의 포인터가 연결 리스트에서 자신보다 오른쪽에 있는 노드들 중 가장 큰 값을 가진 노드를 가리키도록 만드는 것입니다.

예시를 통해 문제를 이해해 보겠습니다.

그림에서 확인할 수 있듯이, 연결 리스트의 각 노드가 가진 임의 포인터는 자신의 오른쪽에 위치한 노드들 중 가장 큰 값을 가리킵니다.

12 -> 76, 76 -> 54, 54 -> 8, 8 -> 41

문제 해결 접근 방법

이 문제를 해결하려면 각 노드의 오른쪽에 있는 원소들 중 최댓값을 찾아야 합니다. 이를 위해 연결 리스트를 역방향으로 순회하면서 지금까지 살펴본 노드 중 최댓값을 계속 추적하고, 각 노드를 지날 때마다 해당 노드의 임의 포인터가 현재 추적 중인 최댓값 노드를 가리키도록 설정합니다.

전체 알고리즘을 단계별로 정리하면 다음과 같습니다.

연결 리스트 전체를 뒤집습니다.
뒤집힌 리스트의 첫 번째 노드를 최댓값 노드(max)로 지정합니다.
두 번째 노드부터 끝까지 순회하면서 각 노드의 임의 포인터를 현재 max 노드에 연결하고, 현재 노드의 값이 max 노드의 값보다 크면 max를 현재 노드로 갱신합니다.
순회가 끝나면 리스트를 다시 원래 순서대로 뒤집어 반환합니다.

구현 예제

위에서 설명한 해결 방법을 구현한 C++ 프로그램입니다.

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node* next, *arbitrary;
};
Node* reverseList(Node *head){
    Node *prev = NULL, *current = head, *next;
    while (current != NULL){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}
Node* populateArbitrary(Node *head){
    head = reverseList(head);
    Node *max = head;
    Node *temp = head->next;
    while (temp != NULL){
        temp->arbitrary = max;
        if (max->data < temp->data)
            max = temp;
        temp = temp->next;
    }
    return reverseList(head);
}
Node *insertNode(int data) {
    Node *new_node = new Node;
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
int main() {
    Node *head = insertNode(12);
    head->next = insertNode(76);
    head->next->next = insertNode(54);
    head->next->next->next = insertNode(8);
    head->next->next->next->next = insertNode(41);
    head = populateArbitrary(head);
    printf("Linked List with Arbitrary Pointer: \n");
    while (head!=NULL){
        cout<<head->data<<"->";
        if (head->next)
            cout<<head->next->data;
        else
            cout<<"NULL";
        cout<<": "<<head->data<<"->";
        if (head->arbitrary)
            cout<<head->arbitrary->data;
        else
            cout<<"NULL";
        cout << endl;
        head = head->next;
    }
    return 0;
}

실행 결과

출력 형식을 살펴보면, 콜론(:) 왼쪽은 노드와 그 다음 노드의 연결 관계를, 오른쪽은 해당 노드와 임의 포인터가 가리키는 노드의 관계를 나타냅니다.

Linked List with Arbitrary Pointer:
12->76: 12->76
76->54: 76->54
54->8: 54->41
8->41: 8->41
41->NULL: 41->NULL

복잡도 분석

이 알고리즘은 연결 리스트를 두 번 뒤집고 한 번 순회하므로 시간 복잡도는 O(n)입니다. 또한 새로운 노드를 추가로 생성하지 않고 기존 포인터만 조작하기 때문에 공간 복잡도는 O(1)로 매우 효율적입니다.