資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 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
對於此問題，想到的一種方法是跟蹤列表，並在子列表的大小達到 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 和其他語言）中編寫相同的程式。我們希望您覺得本文有所幫助。
更新於: 2021年11月29日
209 次檢視
廣告