문제 개요
다음과 같은 형태의 연결 리스트가 있다고 가정해 보겠습니다.
l1 → l2 → l3 → l4 → … → l(n-1) → ln
이 리스트를 다음과 같은 형태로 재배열해야 합니다.
l1 → ln → l2 → l(n-1) → …
여기서 중요한 제약 조건은 노드에 저장된 값 자체는 수정할 수 없고, 노드 간의 연결 구조만 변경할 수 있다는 점입니다.
예를 들어, 입력 리스트가 [1, 2, 3, 4, 5]라면 출력 결과는 [1, 5, 2, 4, 3]이 됩니다. 즉, 앞쪽 노드와 뒤쪽 노드를 번갈아 배치하는 방식입니다.
해결 전략
이 문제는 크게 세 단계로 나누어 해결할 수 있습니다.
1단계: 중간 지점 찾기 (느린/빠른 포인터)
두 개의 포인터 slow와 fast를 사용합니다. fast는 한 번에 두 칸씩 이동하고 slow는 한 칸씩 이동하므로, fast가 리스트 끝에 도달하면 slow는 정확히 중간에 위치하게 됩니다.
2단계: 후반부 리스트 역순으로 뒤집기
중간 지점 이후의 후반부 리스트를 재귀적으로 역순(reverse) 처리합니다. reverse 메서드는 head와 prev 두 개의 매개변수를 받아 다음과 같이 동작합니다.
- head가 null이면 prev를 반환합니다.
- temp에 head의 다음 노드를 저장합니다.
- head의 next를 prev로 설정하고, prev를 head로 갱신합니다.
- reverse(temp, prev)를 재귀 호출하여 계속 진행합니다.
3단계: 두 리스트 교차 병합
앞쪽 절반(정방향)과 뒤쪽 절반(역방향)을 번갈아 연결하여 최종 결과를 만듭니다. temp1과 temp2 임시 포인터를 활용해 기존 연결을 보존하면서 순서대로 엮어갑니다.
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){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* successor = NULL;
ListNode* reverse(ListNode* head, ListNode* prev = NULL){
if(!head)return prev;
ListNode* temp = head->next;
head->next = prev;
prev = head;
return reverse(temp, prev);
}
void reorderList(ListNode* head) {
if(!head)return;
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
fast = reverse(slow->next);
slow->next = NULL;
slow = head;
ListNode *temp1, *temp2;
while(fast){
temp1 = slow->next;
temp2 = fast->next;
slow->next = fast;
fast->next = temp1;
slow = temp1;
fast = temp2;
}
}
};
main(){
vector<int> v = {1,2,3,4,5};
ListNode *h1 = make_list(v);
Solution ob;
(ob.reorderList(h1));
print_list(h1);
}실행 결과 확인
입력
[1,2,3,4,5]
출력
[1, 5, 2, 4, 3]
복잡도 분석
- 시간 복잡도: O(n) — 리스트를 세 번 순회하지만 각각 선형 시간이 걸립니다.
- 공간 복잡도: O(1) — 추가 노드 없이 기존 노드의 포인터만 변경하므로 상수 공간만 사용합니다.
이 알고리즘은 값 수정 없이 포인터 조작만으로 문제를 해결하며, LeetCode 143번 'Reorder List' 문제의 표준적인 풀이 방식이기도 합니다.