C++로 연결 리스트의 첫 번째 요소를 끝으로 이동하는 방법

연결 리스트(Linked List)가 주어졌을 때, 첫 번째 요소를 리스트의 맨 끝으로 이동하는 문제를 해결해 보겠습니다. 먼저 예시를 통해 동작을 살펴보겠습니다.

입력

1 -> 2 -> 3 -> 4 -> 5 -> NULL

출력

2 -> 3 -> 4 -> 5 -> 1 -> NULL

알고리즘

첫 번째 노드를 끝으로 이동하는 과정은 다음 단계로 진행됩니다.

• 연결 리스트를 초기화합니다.

• 리스트가 비어 있거나 노드가 하나뿐이라면 이동할 필요가 없으므로 함수를 종료합니다.

• 리스트를 순회하여 마지막 노드를 찾습니다.

• 두 번째 노드를 새로운 헤드(head)로 지정합니다.

• 첫 번째 노드의 next를 NULL로, 마지막 노드의 next를 기존 첫 번째 노드로 변경하여 링크를 갱신합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void moveFirstNodeToEnd(struct Node** head) {
    if (*head == NULL || (*head)->next == NULL) {
        return;
    }
    struct Node* firstNode = *head;
    struct Node* lastNode = *head;
    while (lastNode->next != NULL) {
        lastNode = lastNode->next;
    }
    *head = firstNode->next;
    firstNode->next = NULL;
    lastNode->next = firstNode;
}
void addNewNode(struct Node** head, int new_data) {
    struct Node* newNode = new Node;
    newNode->data = new_data;
    newNode->next = *head;
    *head = newNode;
}
void printLinkedList(struct Node* node) {
    while (node != NULL) {
        cout << node->data << "->";
        node = node->next;
    }
    cout << "NULL" << endl;
}
int main() {
    struct Node* head = NULL;
    addNewNode(&head, 1);
    addNewNode(&head, 2);
    addNewNode(&head, 3);
    addNewNode(&head, 4);
    addNewNode(&head, 5);
    addNewNode(&head, 6);
    addNewNode(&head, 7);
    addNewNode(&head, 8);
    addNewNode(&head, 9);
    moveFirstNodeToEnd(&head);
    printLinkedList(head);
    return 0;
}

실행 결과

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

8->7->6->5->4->3->2->1->9->NULL

예제에서는 addNewNode 함수가 새 노드를 항상 헤드 앞에 삽입하므로, 1부터 9까지 순서대로 추가한 결과 리스트는 9 -> 8 -> ... -> 1 -> NULL이 됩니다. 이후 moveFirstNodeToEnd 함수가 첫 번째 노드(9)를 끝으로 이동시켜 최종적으로 8 -> 7 -> ... -> 1 -> 9 -> NULL이 출력되는 것을 확인할 수 있습니다.

복잡도 분석

이 알고리즘은 마지막 노드를 찾기 위해 리스트 전체를 한 번 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 연결 리스트의 노드 개수입니다. 추가적인 메모리 사용 없이 기존 노드들의 포인터만 재조정하므로 공간 복잡도는 O(1)입니다.