연결 리스트(Linked List)가 주어졌을 때, 인접한 두 노드를 서로 교환하고 새로운 헤드(head)를 반환하는 문제를 살펴보겠습니다. 이때 중요한 제약 조건은 노드의 값(value)을 수정할 수 없고, 노드 자체의 연결 구조(포인터)만 변경해야 한다는 점입니다.
예를 들어 입력 리스트가 [1,2,3,4]라면, 두 노드씩 짝지어 교환한 결과 리스트는 [2,1,4,3]이 됩니다.
문제 해결 접근 방법
이 문제는 더미(dummy) 노드를 활용하면 깔끔하게 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- head가 존재하지 않으면(null) 그대로 head를 반환합니다.
- first := head, second := head의 다음 노드로 설정하고, 값이 -1인 새로운 더미 노드를 생성합니다.
- 더미 노드의 next를 first로 지정하고, prev := dummy로 초기화합니다.
- second가 null이 아닌 동안 다음 과정을 반복합니다.
- temp := second의 다음 노드를 임시 저장합니다.
- first->next = second->next 로 첫 번째 노드의 연결을 재조정합니다.
- second->next = first 로 두 노드의 순서를 뒤바꿉니다.
- prev->next = second 로 이전 노드와의 연결을 갱신합니다.
- prev := first 로 prev 포인터를 이동합니다.
- temp가 null이 아니면 first := temp, second := temp의 다음 노드로 갱신하고, 그렇지 않으면 반복을 종료합니다.
- 최종적으로 더미 노드의 next를 반환하면 교환이 완료된 리스트의 헤드를 얻을 수 있습니다.
더미 노드를 사용하는 이유
헤드 노드 자체도 교환 대상이기 때문에, 헤드 앞에 가상의 더미 노드를 두면 첫 번째 쌍과 이후의 쌍을 동일한 로직으로 처리할 수 있습니다. 이렇게 하면 '헤드가 바뀌는 특수 경우'를 별도로 처리할 필요가 없어 코드가 훨씬 단순해집니다.
C++ 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head){
ListNode *ptr = head;
cout << "[";
while(ptr->next){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head)return head;
ListNode* first= head;
ListNode* second = head->next;
ListNode* dummy = new ListNode(-1);
dummy->next = first;
ListNode* prev = dummy;
while(second){
ListNode* temp = second->next;
first->next = second->next;
second->next = first;
prev->next = second;
prev = first;
if(temp){
first = temp;
second = temp ->next;
}
else break;
}
return dummy->next;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5,6,7,8};
ListNode *head = make_list(v);
print_list(ob.swapPairs(head));
}입력
[1,2,3,4,5,6,7,8]
출력
[2,1,4,3,6,5,8,7]
복잡도 분석
이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 노드 개수가 홀수일 경우 마지막 남은 노드는 그대로 유지되므로, [1,2,3]이 입력되면 [2,1,3]이 출력됩니다.