연결 리스트가 하나 주어져 있다고 가정해 봅시다. 이 리스트를 오른쪽으로 k칸 회전시켜야 하며, k의 값은 항상 양수입니다. 예를 들어 리스트가 [1 -> 2 -> 3 -> 4 -> 5 -> NULL]이고 k = 2라면, 출력 결과는 [4 -> 5 -> 1 -> 2 -> 3 -> NULL]이 됩니다.
알고리즘 접근 방식
이 문제를 효율적으로 해결하는 핵심 아이디어는 리스트를 임시로 원형 연결 리스트로 만드는 것입니다. 마지막 노드가 첫 번째 노드를 가리키게 한 뒤, 적절한 위치에서 리스트를 다시 끊어주면 회전된 결과를 얻을 수 있습니다. 단계별로 살펴보겠습니다.
- 리스트가 비어 있다면 NULL을 반환합니다.
- len := 1로 초기화합니다.
- tail이라는 노드를 생성하고 head로 설정합니다.
- tail의 next가 NULL이 아닌 동안 반복합니다.
- len을 1 증가시킵니다.
- tail := tail의 next
- tail의 next를 head로 설정하여 리스트를 원형으로 만듭니다.
- k := k mod len (k가 리스트 길이보다 클 경우 불필요한 순환을 제거)
- newHead := NULL
- i를 0부터 len - k 미만까지 반복하며 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]
복잡도 분석
이 알고리즘은 리스트를 한 번 순회하여 길이를 구하고, 다시 한 번 순회하여 새로운 시작점을 찾으므로 시간 복잡도는 O(n)입니다. 여기서 n은 리스트의 노드 개수입니다. 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)로, 매우 효율적인 방법입니다.