이 기사에서 우리는 단일 연결 목록을 다루며 작업은 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
이 문제에 대해 생각나는 한 가지 접근 방식은 목록을 추적하고 하위 목록의 크기가 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++ 프로그램과 이 문제를 해결한 완전한 접근 방식( Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.