이 글에서는 단일 연결 리스트(singly linked list)의 노드 연결을 반대로 뒤집는 방법을 다룹니다. 목표는 주어진 단일 연결 리스트를 역순으로 변환하는 함수를 작성하는 것입니다.
입력: 연결 리스트: 1->2->3->4->NULL 출력: 함수 실행 후: 4->3->2->1->NULL
해결 접근 방식
연결 리스트를 뒤집는 방법은 여러 가지가 있습니다. 가장 먼저 떠오르는 간단한 방법은 리스트를 순회하면서 지나가는 경로상의 링크를 그때그때 뒤집는 것입니다. 이번 글에서는 세 가지 방법을 살펴보겠습니다.
방법 1: 반복문을 이용한 단순 순회
리스트를 처음부터 끝까지 순회하면서, 각 노드의 next 포인터를 이전 노드를 가리키도록 변경하는 방식입니다. 세 개의 포인터(prev, curr, temp)를 활용해 링크 방향을 하나씩 바꿔 나갑니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data) {
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
// 연결 리스트 출력 함수
void reverse() {
auto curr = head; // 현재 포인터
Node* prev = NULL; // 이전 포인터
while(curr) {
auto temp = curr -> next;
curr -> next = prev;
prev = curr;
head = prev;
curr = temp;
}
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data) {
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList list;
list.push(20);
list.push(4);
list.push(15);
list.push(85);
list.print();
list.reverse();
cout << "\n";
list.print();
}실행 결과
85 15 4 20 20 4 15 85
이 방법은 리스트를 한 번만 순회하면서 동시에 뒤집기 때문에 효율적입니다. 시간 복잡도는 O(N)(N은 리스트의 크기)이며, 추가 메모리도 거의 사용하지 않아 가장 널리 쓰이는 방식입니다.
방법 2: 스택(Stack) 활용
스택의 LIFO(후입선출) 특성을 이용하면 리스트를 자연스럽게 역순으로 꺼낼 수 있습니다. 모든 노드를 스택에 저장한 뒤, 스택에서 하나씩 pop하면서 새로운 순서로 연결합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data) {
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
// 연결 리스트 출력 함수
void reverse() {
auto curr = head; // 현재 포인터
Node* prev = NULL; // 이전 포인터
stack<Node *> s;
while(curr) {
s.push(curr);
curr = curr -> next;
}
prev = s.top();
head = prev;
s.pop();
while(!s.empty()) {
auto temp = s.top();
s.pop();
prev -> next = temp;
prev = temp;
}
prev -> next = NULL;
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data) {
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList list;
list.push(20);
list.push(4);
list.push(15);
list.push(85);
list.print();
list.reverse();
cout << "\n";
list.print();
}
실행 결과
85 15 4 20 20 4 15 85
코드 설명
이 방법은 리스트를 순회하면서 모든 노드를 스택에 저장하고, 이후 스택에서 노드를 하나씩 꺼내(pop) 역순으로 연결합니다. 시간 복잡도 역시 O(N)이지만, 모든 노드를 스택에 보관해야 하므로 O(N)의 추가 공간이 필요하다는 점이 첫 번째 방법과 다릅니다.
방법 3: 재귀(Recursion) 활용
재귀 호출도 내부적으로 콜 스택(call stack)을 사용하기 때문에, 스택 기반 접근과 같은 원리를 재귀로 구현할 수 있습니다. 리스트 끝까지 재귀적으로 들어간 뒤, 돌아오는 과정에서 링크를 뒤집습니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data) {
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
// 재귀적으로 리스트를 뒤집는 함수
void rreverse(Node *curr, Node *prev) {
if(curr == NULL) {
head = prev;
return;
}
rreverse(curr -> next, curr);
curr -> next = prev;
prev -> next = NULL;
}
void reverse() {
auto curr = head; // 현재 포인터
Node* prev = NULL; // 이전 포인터
rreverse(curr -> next, curr);
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data) {
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList list;
list.push(20);
list.push(4);
list.push(15);
list.push(85);
list.print();
list.reverse();
cout << "\n";
list.print();
}실행 결과
85 15 4 20 20 4 15 85
재귀 방식도 앞선 방법들과 마찬가지로 시간 복잡도는 O(N)입니다. 다만 재귀 호출 깊이가 리스트 크기만큼 늘어나므로, 리스트가 매우 길 경우 스택 오버플로우(stack overflow)가 발생할 수 있다는 점에 유의해야 합니다.
마무리
이번 글에서는 단일 연결 리스트를 뒤집는 문제를 세 가지 방법—반복문, 스택, 재귀—으로 해결해 보았습니다. 세 방법 모두 시간 복잡도는 O(N)으로 동일하지만, 추가 메모리 사용량과 구현 난이도가 다르므로 상황에 맞는 방법을 선택하는 것이 중요합니다. 같은 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.