C++로 두 개의 연결 리스트를 비교해 각 노드의 최댓값으로 새 연결 리스트 만들기

이 튜토리얼에서는 주어진 두 개의 연결 리스트(Linked List)를 활용해 새로운 연결 리스트를 만드는 C++ 프로그램을 작성하는 방법을 알아보겠습니다.

크기가 같은 두 개의 연결 리스트가 주어졌을 때, 각 위치에서 두 노드 중 더 큰 값을 선택해 하나의 새로운 연결 리스트를 구성하는 것이 이번 문제의 목표입니다.

문제 해결 접근 방식

다음 단계를 따라 문제를 해결할 수 있습니다.

• 노드(Node) 구조체를 정의합니다.

• 동일한 크기의 두 개의 연결 리스트를 생성합니다.

• 연결 리스트를 순회하면서 아래 작업을 반복 수행합니다.

  • 두 리스트의 현재 노드 값 중 최댓값을 찾습니다.

  • 최댓값을 담은 새 노드를 생성합니다.

  • 새 노드를 결과 연결 리스트에 추가합니다.

• 완성된 새 연결 리스트를 출력합니다.

예제 코드

실제 동작하는 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
void insertNewNode(Node** root, int data) {
    Node *ptr, *temp;
    temp = new Node;
    temp->data = data;
    temp->next = NULL;
    if (*root == NULL) {
        *root = temp;
    }
    else {
        ptr = *root;
        while (ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = temp;
    }
}
Node* getNewLinkedList(Node* root1, Node* root2) {
    Node *ptr1 = root1, *ptr2 = root2, *ptr;
    Node *root = NULL, *temp;
    while (ptr1 != NULL) {
        temp = new Node;
        temp->next = NULL;
        if (ptr1->data < ptr2->data) {
            temp->data = ptr2->data;
        }
        else {
            temp->data = ptr1->data;
        }
        if (root == NULL) {
            root = temp;
        }
        else {
            ptr = root;
            while (ptr->next != NULL) {
                ptr = ptr->next;
            }
            ptr->next = temp;
        }
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return root;
}
void printLinkedList(Node* root) {
    while (root != NULL) {
        cout << root->data << "->";
        root = root->next;
    }
    cout << "NULL" << endl;
}
int main() {
    Node *root1 = NULL, *root2 = NULL, *root = NULL;
    insertNewNode(&root1, 1);
    insertNewNode(&root1, 2);
    insertNewNode(&root1, 3);
    insertNewNode(&root1, 4);
    cout << "First Linked List: ";
    printLinkedList(root1);
    insertNewNode(&root2, 0);
    insertNewNode(&root2, 5);
    insertNewNode(&root2, 2);
    insertNewNode(&root2, 6);
    cout << "Second Linked List: ";
    printLinkedList(root2);
    root = getNewLinkedList(root1, root2);
    cout << "New Linked List: ";
    printLinkedList(root);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

First Linked List: 1->2->3->4->NULL
Second Linked List: 0->5->2->6->NULL
New Linked List: 1->5->3->6->NULL

코드 설명

insertNewNode 함수는 연결 리스트 끝에 새 노드를 추가하는 역할을 합니다. 리스트가 비어 있으면 첫 번째 노드로 설정하고, 그렇지 않으면 마지막 노드까지 이동한 뒤 새 노드를 연결합니다.

getNewLinkedList 함수가 이 튜토리얼의 핵심입니다. 두 개의 포인터(ptr1, ptr2)로 각 리스트를 동시에 순회하면서, 현재 위치의 두 노드 값을 비교해 더 큰 값을 새 노드에 저장하고 결과 리스트에 차례대로 추가합니다.

printLinkedList 함수는 리스트의 모든 데이터를 순서대로 출력한 후 마지막에 NULL을 표시해 리스트의 끝을 나타냅니다.

마무리

이번 튜토리얼에서는 두 개의 연결 리스트를 한 칸씩 비교하며 각 노드의 최댓값만 모아 새로운 연결 리스트를 만드는 방법을 배웠습니다. 시간 복잡도는 O(n)으로 리스트의 길이에 비례하며, 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.