Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 연결 리스트 구간 뒤집기 II — 한 번의 순회로 m부터 n까지 역순 정렬하기

연결 리스트(Linked List)가 주어졌을 때, 위치 m부터 n까지의 노드를 딱 한 번의 순회(one pass)만으로 뒤집는 문제를 살펴보겠습니다.

예를 들어 리스트가 [1, 2, 3, 4, 5]이고 m = 2, n = 4라면, 2번째부터 4번째 노드만 역순으로 배치되어 결과는 [1, 4, 3, 2, 5]가 됩니다.

알고리즘 접근 방식

이 문제는 재귀(recursion)를 활용해 해결할 수 있습니다. 핵심 아이디어는 전체 리스트를 뒤집는 대신, 앞쪽 m-1개 노드는 그대로 두고 n개의 노드만 부분적으로 뒤집는 것입니다.

구현에는 두 개의 메서드가 사용됩니다.

  • reverseBetween(): 메인 메서드로, 뒤집기를 시작할 위치(m)까지 재귀적으로 이동합니다.
  • reverseN(): 현재 노드부터 n개의 노드를 실제로 뒤집는 메서드입니다.

reverseN()의 동작 과정

  1. n = 1이면, 전역 포인터 successor에 head의 다음 노드를 저장하고 head를 반환합니다. 이때 successor는 뒤집힌 구간 뒤에 이어질 나머지 리스트를 가리킵니다.
  2. 그렇지 않으면 last = reverseN(head->next, n - 1)을 호출해 재귀적으로 뒤집기를 진행합니다.
  3. 재귀가 풀리면서 head->next->next = head로 포인터 방향을 반대로 돌리고, head->next = successor로 뒤집힌 구간의 끝을 나머지 리스트와 연결한 뒤 last를 반환합니다.

reverseBetween()의 동작 과정

  1. m = 1이면 시작 위치가 첫 번째 노드이므로 곧바로 reverseN(head, n)을 호출하여 반환합니다.
  2. m > 1이면 head->next = reverseBetween(head->next, m - 1, n - 1)을 호출해 시작 지점까지 한 칸씩 이동하며, 이동할 때마다 m과 n을 함께 1씩 줄여 상대적인 구간 길이를 유지합니다.

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

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* reverseN(ListNode* head, int n ){
            if(n == 1){
               successor = head->next;
               return head;
            }
            ListNode* last = reverseN(head->next, n - 1);
            head->next->next = head;
            head->next = successor;
            return last;
         }
         ListNode* reverseBetween(ListNode* head, int m, int n) {
            if(m == 1){
               return reverseN(head, n);
            }
            head->next = reverseBetween(head->next, m - 1, n - 1);
            return head;
         }
   };
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,7,8};
   ListNode *head = make_list(v);
   print_list(ob.reverseBetween(head, 2, 6));
}

입력

[1,2,3,4,5,6,7,8]
2
6

출력

[1, 6, 5, 4, 3, 2, 7, 8]

동작 설명

입력 리스트 [1, 2, 3, 4, 5, 6, 7, 8]에서 m = 2, n = 6이므로, 2번째 노드(2)부터 6번째 노드(6)까지만 뒤집힙니다. 따라서 [6, 5, 4, 3, 2] 구간이 역순으로 배치되고, 앞의 1과 뒤의 7, 8은 원래 순서를 유지하여 최종 출력은 [1, 6, 5, 4, 3, 2, 7, 8]이 됩니다.

이 방식은 각 노드를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(n), 재귀 호출 스택으로 인한 공간 복잡도는 O(n)입니다.