연결 리스트(Linked List)가 주어졌을 때 마지막 노드를 리스트의 맨 앞으로 이동해야 합니다. 먼저 예시를 통해 문제를 살펴보겠습니다.
입력
1 -> 2 -> 3 -> 4 -> 5 -> NULL
출력
5 -> 1 -> 2 -> 3 -> 4 -> NULL
알고리즘
연결 리스트를 초기화합니다.
리스트가 비어 있거나 노드가 하나뿐이라면 아무 작업 없이 종료합니다.
연결 리스트에서 마지막 노드와 마지막에서 두 번째 노드를 찾습니다.
마지막 노드를 새로운 헤드(head)로 지정합니다.
마지막에서 두 번째 노드의 next 포인터를 NULL로 갱신합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
// 마지막 노드를 맨 앞으로 이동하는 함수
void moveLastNodeToFront(struct Node** head) {
// 노드가 없거나 하나뿐인 경우 그대로 반환
if (*head == NULL || (*head)->next == NULL) {
return;
}
struct Node* secondLastNode = *head;
struct Node* lastNode = *head;
// 마지막 노드와 마지막에서 두 번째 노드 탐색
while (lastNode->next != NULL) {
secondLastNode = lastNode;
lastNode = lastNode->next;
}
// 마지막에서 두 번째 노드의 연결을 끊음
secondLastNode->next = NULL;
// 기존 헤드를 마지막 노드 뒤에 연결
lastNode->next = *head;
// 마지막 노드를 새로운 헤드로 지정
*head = lastNode;
}
// 새 노드를 리스트 맨 앞에 추가하는 함수
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);
moveLastNodeToFront(&head);
printLinkedList(head);
return 0;
}
참고: 원본 코드의 함수 이름은 moveFirstNodeToEnd였지만, 실제 동작은 마지막 노드를 맨 앞으로 이동하는 것이므로 이 글에서는 의미에 맞게 moveLastNodeToFront로 수정했습니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
1->9->8->7->6->5->4->3->2->NULL
addNewNode 함수는 항상 리스트의 맨 앞에 새 노드를 삽입하므로, 1부터 9까지 차례대로 추가하면 실제 리스트는 9 → 8 → … → 1 순서가 됩니다. 이후 마지막 노드인 1이 맨 앞으로 이동하면서 위와 같은 결과가 나옵니다.
복잡도 분석
시간 복잡도: O(n) — 마지막 노드를 찾기 위해 리스트 전체를 한 번 순회합니다.
공간 복잡도: O(1) — 포인터 몇 개만 사용하므로 추가 메모리가 거의 필요하지 않습니다.