C++를 사용하여 주어진 크기로 역방향 연결 목록 그룹화

이 기사에서는 단일 연결 목록을 다루고 작업은 k 그룹의 목록을 뒤집는 것입니다. 예를 들어 -

Input: 1->2->3->4->5->6->7->8->NULL, K = 3
Output: 3->2->1->6->5->4->8->7->NULL

Input: 1->2->3->4->5->6->7->8->NULL, K = 5
Output: 5->4->3->2->1->8

이 문제에 대해 생각나는 한 가지 접근 방식은 목록을 tail하고 하위 목록의 크기가 k에 도달하면 목록을 뒤집어서 계속하는 것입니다.

해결책을 찾는 방법

이 방법을 사용하면 일반적으로 목록을 반복하고 하위 목록의 요소 수를 계산하는 카운터를 유지합니다. 카운터가 k개에 도달하면 해당 부분을 반전시킵니다.

예제

#include <bits/stdc++.h>
using namespace std;
class Node {
   public:
   int data;
   Node* next;
};
Node* reverse(Node* head, int k) {
   if (!head)
      return NULL;
   Node* curr = head;
   Node* next = NULL;
   Node* prev = NULL;
   int count = 0;
   while (curr != NULL && count < k) { // we reverse the list till our count is less than k
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
      count++;
   }
   if (next != NULL) // if our link list has not ended we call reverse function again
      head->next = reverse(next, k);
   return prev;
}
void push(Node** head_ref, int new_data) { // function for pushing data in the list
   Node* new_node = new Node();
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
void printList(Node* node) { // function to print linked list

   while (node != NULL) {
      cout << node->data << " ";
      node = node->next;
   }
   cout << "\n";
}
int main() {
   Node* head = NULL;

   int k = 3; // the given k

   push(&head, 8);
   push(&head, 7);
   push(&head, 6);
   push(&head, 5);
   push(&head, 4);
   push(&head, 3);
   push(&head, 2);
   push(&head, 1);

   cout << "Original list \n";
   printList(head);

   head = reverse(head, k); // this function will return us our new head
   cout << "New list \n";
   printList(head);
   return (0);
}

출력

Original list
1 2 3 4 5 6 7 8
New list
3 2 1 6 5 4 8 7

위 방법의 시간 복잡도는 O(N)입니다. 여기서 N은 주어진 목록의 크기이고 이 방법은 재귀에 적합합니다. 이 접근 방식은 더 높은 제약 조건에도 적용됩니다.

위 코드에 대한 설명

이 방법에서는 배열을 반복하고 카운터 변수가 k보다 작을 때까지 계속 반전합니다. 카운터가 k 값에 도달하면 또 다른 반전 함수를 호출하여 이 하위 목록의 마지막 노드를 다음 반전된 하위 목록의 첫 번째 노드에 연결합니다. 이는 재귀적으로 수행됩니다.

결론

이 기사에서는 재귀를 사용하여 주어진 크기의 그룹별로 연결 목록을 뒤집는 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 방법(일반)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

위 내용은 C++를 사용하여 주어진 크기로 역방향 연결 목록 그룹화의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!