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

이 문제에서는 연결 리스트의 헤드에 대한 포인터와 정수 k를 얻습니다. 크기가 k인 그룹에서는 연결된 목록을 뒤집어야 합니다. 예를 들어 -

Input : 1 <-> 2 <-> 3 <-> 4 <-> 5 (doubly linked list), k = 3
Output : 3 <-> 2 <-> 1 <-> 5 <-> 4

해결책을 찾는 방법

이 문제에서 우리는 이 문제를 해결하기 위한 재귀 알고리즘을 공식화할 것입니다. 이 방법에서는 재귀를 사용하고 재귀를 사용하여 문제를 해결합니다.

Example

#include <iostream>
using namespace std;
struct Node {
   int data;
   Node *next, *prev;
};
// push function to push a node into the list
Node* push(Node* head, int data) {
   Node* new_node = new Node();
   new_node->data = data;
   new_node->next = NULL;
   Node* TMP = head;
   if (head == NULL) {
      new_node->prev = NULL;
      head = new_node;
      return head;
   }
   while (TMP->next != NULL) { // going to the last node
      TMP = TMP->next;
   }
   TMP->next = new_node;
   new_node->prev = TMP;
   return head; // return pointer to head
}
// function to print given list
void printDLL(Node* head) {
   while (head != NULL) {
   cout << head->data << " ";
   head = head->next;
}
cout << endl;
}
Node* revK(Node* head, int k) {
   if (!head)
      return NULL;
   head->prev = NULL;
   Node *TMP, *CURRENT = head, *newHead;
   int count = 0;
   while (CURRENT != NULL && count < k) { // while our count is less than k we simply reverse                                                 the nodes.
      newHead = CURRENT;
      TMP = CURRENT->prev;
      CURRENT->prev = CURRENT->next;
      CURRENT->next = TMP;
      CURRENT = CURRENT->prev;
      count++;
   }
   if (count >= k) {
      head->next = revK(CURRENT, k); // now when if the count is greater or equal
      //to k we connect first head to next head
   }
   return newHead;
}
int main() {
   Node* head;
   for (int i = 1; i <= 5; i++) {
      head = push(head, i);
   }
   cout << "Original List : ";
   printDLL(head);
   cout << "\nModified List : ";
   int k = 3;
   head = revK(head, k);
   printDLL(head);
}

Output

Original List : 1 2 3 4 5
Modified List : 3 2 1 5 4

위 코드 설명

이 방법에서는 목록을 반복하고 개수가 k보다 작을 때까지 반복합니다. head -> next에 값을 제공하는 재귀 호출을 합니다(여기서는 순회하는 동안 목록을 뒤집는 것뿐입니다. 그러나 k에 도달하면 다른 목록의 k번째 요소를 가리키는 헤드를 만들어야 합니다. 예를 들어 목록이 1인 경우 2 3 4 5, k는 3입니다. 중간 요소를 3 2 1로 바꾸었지만 이제 4를 가리키는 1이 필요합니다. 해당 요소도 반전되기 때문입니다. 그래서 재귀 호출을 사용하고 다음과 같은 경우 추가로 만듭니다. 진술).

결론

이 기사에서는 Recursion을 사용하여 문제를 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이를 해결하기 위한 완전한 접근 방식을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

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