연결 리스트(linked list)가 하나 주어져 있다고 가정해 봅시다. 우리가 해야 할 일은 이 리스트를 오른쪽으로 k칸 회전시키는 것입니다. 단, k는 음수가 아닌 값입니다.
예를 들어 리스트가 [1, 2, 3, 4, 5, NULL]이고 k = 2라면, 마지막 두 개의 노드(4, 5)가 앞으로 이동하여 출력 결과는 [4, 5, 1, 2, 3, NULL]이 됩니다.
알고리즘 접근 방식
이 문제는 리스트를 임시로 원형(circular) 리스트로 만든 뒤 적절한 위치에서 끊어내는 방식으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 리스트가 비어 있다면 null을 그대로 반환합니다.
- len을 1로 초기화하고, tail이라는 포인터를 head로 설정합니다.
- tail->next가 null이 아닐 동안 반복하면서 len을 1씩 증가시키고 tail을 다음 노드로 이동시킵니다. (이 과정에서 전체 길이와 마지막 노드를 얻습니다.)
- tail->next를 head로 연결하여 리스트를 원형으로 만듭니다.
- k를 k mod len으로 갱신합니다. (k가 리스트 길이보다 큰 경우를 처리)
- i가 0부터 len - k - 1까지 반복하면서 tail을 다음 노드로 이동시킵니다.
- newHead를 tail->next로 설정합니다. (새로운 시작점)
- tail->next를 null로 설정하여 원형 연결을 끊습니다.
- newHead를 반환합니다.
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* rotateRight(ListNode* head, int k) {
if(!head) return head;
int len = 1;
ListNode* tail = head;
while(tail->next){
len++;
tail = tail->next;
}
tail->next = head;
k %= len;
ListNode* newHead = NULL;
for(int i = 0; i < len - k; i++){
tail = tail->next;
}
newHead = tail->next;
tail->next = NULL;
return newHead;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5,6,7,8,9};
ListNode *head = make_list(v);
print_list(ob.rotateRight(head, 4));
}입력
[1,2,3,4,5,6,7,8,9] 4
출력
[6, 7, 8, 9, 1, 2, 3, 4]
코드 설명
위 예제에서는 9개의 노드를 가진 리스트 [1, 2, 3, 4, 5, 6, 7, 8, 9]를 오른쪽으로 4칸 회전합니다. 먼저 전체 길이(len = 9)를 계산한 뒤 tail->next를 head에 연결해 원형 리스트로 만듭니다. 그다음 k = 4이므로 len - k = 5번 tail을 앞으로 이동시켜 새로운 시작점 직전 노드에 도달하고, 해당 위치에서 연결을 끊으면 [6, 7, 8, 9, 1, 2, 3, 4, 5] 형태의 회전된 리스트를 얻게 됩니다.
이 알고리즘의 시간 복잡도는 리스트를 한 번 순회하므로 O(n)이며, 추가 공간은 포인터 몇 개만 사용하므로 공간 복잡도는 O(1)입니다.