C++에서 k-그룹의 역 노드

연결 목록이 있다고 가정하면 연결 목록 k의 노드를 한 번에 뒤집고 수정된 목록을 반환해야 합니다. 여기서 k는 양의 정수이고 연결 목록의 길이보다 작거나 같습니다. 따라서 노드의 수가 k의 배수가 아닌 경우에는 결국 남아 있는 노드가 그대로 유지되어야 합니다.

따라서 연결 목록이 [1,2,3,4,5,6,7]이고 k가 3이면 결과는 [3,2,1,6,5,4,7]이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• solve()라는 메소드를 정의합니다. 이것은 연결 리스트의 선두를 취하고 partCount와 k

  를 취합니다.

• partCount가 0이면 head를 반환합니다.

• newHead :=헤드, 이전 :=null, x :=k

• newHead가 null이 아니고 x가 0이 아닌 동안

  • temp :=newHead 다음, nextHead 다음 :=이전

  • 이전 :=newHead, newHead :=임시

• 머리 다음:=solve(newHead, partCount – 1, k)

• 이전으로 돌아가기

• 주요 방법에서 다음을 수행하십시오 -

• return solve(연결 리스트의 선두, 리스트의 길이 / k, k)

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#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, ]