C++ 단일 연결 리스트에서 최솟값과 최댓값 찾는 방법

이 문제에서는 하나의 단일 연결 리스트(singly linked list)가 주어지며, 우리의 과제는 이 연결 리스트 안에서 가장 작은 요소(최솟값)와 가장 큰 요소(최댓값)를 찾아내는 것입니다.

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

입력

연결 리스트 : 5 -> 2 -> 7 -> 3 -> 9 -> 1 -> 4

출력

최솟값 = 1
최댓값 = 9

해결 접근 방법

이 문제를 해결하는 가장 간단한 방법은 연결 리스트를 노드 단위로 순회(traversal)하는 것입니다.

순회를 시작하기 전에 먼저 maxElement와 minElement 변수를 첫 번째 노드의 값(head->data)으로 초기화합니다. 그런 다음 연결 리스트를 한 노드씩 차례대로 탐색하면서 다음 작업을 수행합니다.

• 현재 노드의 값을 maxElement와 비교하여, 더 큰 값을 maxElement 변수에 저장합니다.
• 같은 방식으로 현재 노드의 값을 minElement와 비교하여, 더 작은 값을 minElement 변수에 저장합니다.

모든 노드에 대한 순회가 끝나면 두 변수에 저장된 값을 출력하면 됩니다. 이 알고리즘은 리스트 전체를 한 번만 훑으면 되므로 시간 복잡도는 O(n)입니다.

해결 방법의 동작을 보여주는 프로그램입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void printLargestSmallestLinkedList(struct Node* head) {
    int maxElement = INT_MIN;
    int minElement = INT_MAX;
    while (head != NULL) {
        if (minElement > head->data)
            minElement = head->data;
        if (maxElement < head->data)
            maxElement = head->data;
        head = head->next;
    }
    cout<<"연결 리스트의 최솟값 : "<<minElement<<endl;
    cout<<"연결 리스트의 최댓값 : "<<maxElement<<endl;
}
void push(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = (*head);
    (*head) = newNode;
}
int main() {
    struct Node* head = NULL;
    push(&head, 5);
    push(&head, 2);
    push(&head, 7);
    push(&head, 3);
    push(&head, 9);
    push(&head, 1);
    push(&head, 4);
    printLargestSmallestLinkedList(head);
    return 0;
}

출력 결과

연결 리스트의 최솟값 : 1
연결 리스트의 최댓값 : 9

위 코드에서는 초기값을 각각 INT_MIN(int형의 최솟값)과 INT_MAX(int형의 최댓값)로 설정했습니다. 이렇게 하면 어떤 값이 들어와도 첫 번째 비교에서 반드시 갱신되므로, 빈 리스트가 아닌 경우 항상 올바른 결과를 얻을 수 있습니다. 또한 push 함수는 새 노드를 리스트 맨 앞에 삽입하므로, 입력 순서와 실제 리스트의 순서는 반대가 된다는 점도 참고하세요.