Inhaltsverzeichnis
Methode zum Finden der Lösung
Beispiel
Ausgabe
Erklärung des obigen Codes
Fazit
Heim Backend-Entwicklung C++ Umgekehrte Gruppierung verknüpfter Listen nach gegebener Größe mit C++

Umgekehrte Gruppierung verknüpfter Listen nach gegebener Größe mit C++

Sep 18, 2023 pm 12:17 PM
c语言 链表 Gruppeninversion

Umgekehrte Gruppierung verknüpfter Listen nach gegebener Größe mit C++

In diesem Artikel beschäftigen wir uns mit einer einfach verknüpften Liste und die Aufgabe besteht darin, die Liste in Gruppen von k umzukehren. Zum Beispiel -

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
Nach dem Login kopieren

Für dieses Problem fällt mir ein Ansatz ein, die Liste zu beenden und umzukehren, wenn die Größe der Unterliste k erreicht, und fortzufahren.

Methode zum Finden der Lösung

Mit dieser Methode durchlaufen wir normalerweise die Liste und führen einen Zähler, um die Anzahl der Elemente in der Unterliste zu zählen. Wenn der Zähler einen Zählerstand von k erreicht, invertieren wir diesen Teil.

Beispiel

#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);
}
Nach dem Login kopieren

Ausgabe

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

Nach dem Login kopieren

Die zeitliche Komplexität der obigen Methode beträgt O(N), wobei N die Größe der gegebenen Liste ist und die Methode für die Rekursion geeignet ist. Dieser Ansatz funktioniert auch für höhere Einschränkungen.

Erklärung des obigen Codes

Bei dieser Methode durchlaufen wir das Array und kehren es so lange um, bis unsere Zählervariable kleiner als k ist. Wenn der Zähler den Wert von k erreicht, rufen wir eine weitere Inversionsfunktion auf, um den letzten Knoten dieser Unterliste mit dem ersten Knoten der nächsten invertierten Unterliste zu verbinden. Dies geschieht rekursiv.

Fazit

In diesem Artikel haben wir das Problem der Umkehrung einer verknüpften Liste nach Gruppen einer bestimmten Größe mithilfe der Rekursion gelöst. Wir haben auch ein C++-Programm zur Lösung dieses Problems und eine vollständige Methode zur Lösung dieses Problems (Normal) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Wir hoffen, dass dieser Artikel für Sie hilfreich war.

Das obige ist der detaillierte Inhalt vonUmgekehrte Gruppierung verknüpfter Listen nach gegebener Größe mit C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
2 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Repo: Wie man Teamkollegen wiederbelebt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Abenteuer: Wie man riesige Samen bekommt
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Verwendung der Typedef-Struktur in der C-Sprache Verwendung der Typedef-Struktur in der C-Sprache May 09, 2024 am 10:15 AM

typedef struct wird in der C-Sprache zum Erstellen von Strukturtypaliasen verwendet, um die Verwendung von Strukturen zu vereinfachen. Es weist einem neuen Datentyp ein Alias ​​auf eine vorhandene Struktur zu, indem es den Strukturalias angibt. Zu den Vorteilen gehören verbesserte Lesbarkeit, Wiederverwendung von Code und Typprüfung. Hinweis: Die Struktur muss vor der Verwendung eines Alias ​​definiert werden. Der Alias ​​muss im Programm eindeutig sein und nur innerhalb des Bereichs gültig sein, in dem er deklariert ist.

Der Unterschied zwischen strcpy und strcat in der C-Sprache Der Unterschied zwischen strcpy und strcat in der C-Sprache May 08, 2024 pm 01:03 PM

strcpy kopiert einen String in einen anderen String, während strcat einen String an einen anderen String anhängt. Zu den Hauptunterschieden gehören: unterschiedliche Zwecke, unterschiedliche DST-Parameterverarbeitung und unterschiedliche Sicherheitsaspekte.

Was bedeutet real in der C-Sprache? Was bedeutet real in der C-Sprache? May 09, 2024 pm 12:06 PM

real ist der Datentyp, der zur Darstellung von Gleitkommazahlen mit doppelter Genauigkeit in der Sprache C verwendet wird. Er belegt 8 Bytes, hat eine Genauigkeit von etwa 15 Dezimalstellen und der Bereich beträgt [-1,7976931348623157e+308, 1,7976931348623157e+308].

Was tun, wenn in scanf in der C-Sprache ein Fehler auftritt? Was tun, wenn in scanf in der C-Sprache ein Fehler auftritt? May 09, 2024 am 11:39 AM

In der C-Sprache umfassen die Methoden zur Behandlung von Scanf-Funktionen: 1. Überprüfen Sie die Eingabe; 3. Überprüfen Sie den Rückgabewert. 5. Verwenden Sie die Fehlerbehandlungsfunktion Benutzerdefinierte Fehler behandeln. Um Fehler zu vermeiden, verwenden Sie die richtigen Datentypen, validieren Sie Eingaben sorgfältig, überprüfen Sie Rückgabewerte und behandeln Sie potenzielle Fehler in Ihrem Programm.

So implementieren Sie die Power-Funktion in der C-Sprache So implementieren Sie die Power-Funktion in der C-Sprache May 09, 2024 pm 11:33 PM

In der C-Sprache gibt es zwei Möglichkeiten, die Potenzierungsoperation zu implementieren: Verwenden Sie die Funktion pow(), um die Potenz des zweiten Parameters des ersten Parameters zu berechnen. Definieren Sie eine benutzerdefinierte Potenzfunktion, die rekursiv oder iterativ implementiert werden kann: Die rekursive Methode verdoppelt die Potenz weiterhin, bis sie 0 ist. Die iterative Methode verwendet eine Schleife, um die Basis einzeln zu multiplizieren.

_komplexe Verwendung in C-Sprache _komplexe Verwendung in C-Sprache May 08, 2024 pm 01:27 PM

Der komplexe Typ wird zur Darstellung komplexer Zahlen in der C-Sprache verwendet, einschließlich Real- und Imaginärteilen. Seine Initialisierungsform ist complex_number = 3.14 + 2.71i, auf den Realteil kann über creal(complex_number) und auf den Imaginärteil über cimag(complex_number) zugegriffen werden. Dieser Typ unterstützt gängige mathematische Operationen wie Addition, Subtraktion, Multiplikation, Division und Modulo. Darüber hinaus wird eine Reihe von Funktionen zum Arbeiten mit komplexen Zahlen bereitgestellt, z. B. cpow, csqrt, cexp und csin.

So verwenden Sie „Restrict' in der C-Sprache So verwenden Sie „Restrict' in der C-Sprache May 08, 2024 pm 01:30 PM

Das Schlüsselwort „restrict“ wird verwendet, um den Compiler darüber zu informieren, dass auf eine Variable nur mit einem Zeiger zugegriffen werden kann. Dadurch wird undefiniertes Verhalten verhindert, der Code optimiert und die Lesbarkeit verbessert: Verhindert undefiniertes Verhalten, wenn mehrere Zeiger auf dieselbe Variable zeigen. Um den Code zu optimieren, verwendet der Compiler das Schlüsselwort „restrict“, um den Variablenzugriff zu optimieren. Verbessert die Lesbarkeit des Codes, indem es angibt, dass auf Variablen nur mit einem Zeiger zugegriffen werden kann.

_Was bedeutet bool in der C-Sprache? _Was bedeutet bool in der C-Sprache? May 08, 2024 pm 01:33 PM

_Bool stellt den booleschen Typ in der C-Sprache dar. Es handelt sich um einen einfachen Datentyp, der nur zwei Werte enthält, wahr oder falsch. Er wird verwendet, um die Ergebnisse von Bedingungen oder logischen Ausdrücken darzustellen. Er belegt normalerweise 1 Byte Speicher und kann nur wahr oder falsch speichern falsch. falscher Wert.

See all articles