문제 개요
연결 리스트(Linked List)가 주어졌을 때, 노드들을 k개씩 묶어서 순서를 뒤집고 수정된 리스트를 반환하는 문제입니다. 여기서 k는 양의 정수이며, 연결 리스트의 전체 길이보다 작거나 같아야 합니다.
만약 노드의 총 개수가 k의 배수가 아니라면, 마지막에 남는 노드들은 원래 순서 그대로 유지해야 합니다.
예를 들어, 연결 리스트가 [1,2,3,4,5,6,7]이고 k가 3이라면, 결과는 다음과 같습니다.
[3,2,1,6,5,4,7]
앞의 6개 노드는 3개씩 두 그룹으로 나뉘어 각각 뒤집히지만, 마지막에 남은 노드 7은 원래 위치와 순서를 그대로 유지하는 것을 확인할 수 있습니다.
해결 접근 방법
이 문제는 재귀(Recursion) 방식으로 해결할 수 있습니다. 핵심 아이디어는 리스트를 k개씩 나눌 수 있는 그룹 수만큼 반복적으로 뒤집는 것입니다. 해결 단계는 다음과 같습니다.
solve()라는 메서드를 정의합니다. 이 메서드는 연결 리스트의 헤드(head), 남은 그룹 수(partCount), 그룹 크기(k)를 매개변수로 받습니다.- partCount가 0이면 더 이상 뒤집을 그룹이 없으므로 head를 그대로 반환합니다.
- newHead := head, prev := null, x := k로 초기화합니다.
- newHead가 null이 아니고 x가 0이 아닐 때까지 반복하면서 노드의 포인터 방향을 역순으로 변경합니다.
- temp := newHead의 next 노드 저장
- newHead의 next를 prev로 변경
- prev := newHead, newHead := temp로 이동
- k개의 노드를 모두 뒤집은 후, head의 next를
solve(newHead, partCount - 1, k)의 결과로 연결하여 다음 그룹을 재귀적으로 처리합니다. - 뒤집힌 그룹의 새로운 시작점인 prev를 반환합니다.
메인 함수에서는 먼저 리스트의 전체 길이를 계산한 후, solve(head, length / k, k)를 호출하여 전체 그룹 수만큼 뒤집기를 수행합니다.
C++ 구현 예제
다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
void print_vector(vector<vector<auto>> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
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* solve(ListNode* head, int partitionCount, int k){
if(partitionCount == 0)return head;
ListNode *newHead = head;
ListNode* prev = NULL;
ListNode* temp;
int x = k;
while(newHead && x--){
temp = newHead->next;
newHead->next = prev;
prev = newHead;
newHead = temp;
}
head->next = solve(newHead, partitionCount - 1, k);
return prev;
}
int calcLength(ListNode* head){
int len = 0;
ListNode* curr = head;
while(curr){
len++;
curr = curr->next;
}
return len;
}
ListNode* reverseKGroup(ListNode* head, int k) {
int length = calcLength(head);
return solve(head, length / k, k);
}
};
main(){
vector<int> v = {1,2,3,4,5,6,7};
ListNode *head = make_list(v);
Solution ob;
print_list(ob.reverseKGroup(head, 3));
}입력
1,2,3,4,5,6,7 3
출력
[3, 2, 1, 6, 5, 4, 7]
코드 설명 및 시간 복잡도
위 코드의 동작 흐름을 정리하면 다음과 같습니다.
calcLength(): 연결 리스트를 한 번 순회하며 전체 노드 개수를 계산합니다. 시간 복잡도는 O(n)입니다.reverseKGroup(): 전체 길이를 k로 나누어 뒤집어야 할 그룹 수를 구하고,solve()를 호출합니다.solve(): 각 호출마다 k개의 노드를 제자리(in-place)에서 뒤집습니다. 포인터 조작만 사용하므로 추가 공간은 O(1)이며, 재귀 깊이는 n/k입니다.
전체 시간 복잡도는 O(n), 공간 복잡도는 재귀 스택을 고려하면 O(n/k)입니다. 만약 재귀 대신 반복문 기반으로 구현하면 공간 복잡도를 O(1)로 줄일 수 있습니다.