C++ data structure and algorithm inversion linked list method
- 2020-05-27 06:52:50
- OfStack
In this paper, we illustrate the method of C++ data structure and algorithm to reverse the linked list. I will share it with you for your reference as follows:
Algorithm overview: the implementation is required to reverse a single linked list and consider the time complexity.
Algorithm analysis:
Array method (omitted) :
Save the list elements into an array one at a time, and then rebuild the list in reverse
Comments: implementation logic is the simplest and requires additional memory overhead.
Move pointer:
Reverse the pointer to the list element 1 by 1, starting at the head of the list with 3 Pointers
Comments: no additional memory overhead is required to change the original list.
Recursive:
Recursively, the end of the list is found and the pointer is reversed 1 by 1
Comments: no additional memory overhead, no changes to the original linked list.
Algorithm implementation:
Build a linked list structure
/* The node structure */
struct NODE
{
int data;
struct NODE* next;
};
/* Add elements - The pressure of stack */
void push(NODE** head, int dat) {
struct NODE* new_node = new NODE();
new_node->data = dat;
new_node->next = *head;
*head = new_node;
}
/* Add elements - add */
void add(NODE** head, int dat) {
struct NODE* new_node = new NODE();
new_node->data = dat;
new_node->next = NULL;
if (*head != NULL) {
struct NODE* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
}
else {
*head = new_node;
}
}
Move the cursor
/* Inversion of the list */
void reverse(NODE** head) {
struct NODE* pre = NULL;
struct NODE* cur = *head;
struct NODE* nxt;
while (cur != NULL) {
// Reverse pointer
nxt = cur->next;
cur->next = pre;
// Move the cursor
pre = cur;
cur = nxt;
}
*head = pre;
}
recursive
/* Inversion of the list - Copy the original table to return the reverse table */
NODE* reverse(NODE* head) {
if (head == NULL || head->next == NULL) {
return head;
}
NODE* new_head = reverse(head->next);
// Reverse pointer
head->next->next = head;
head->next = NULL;
return new_head;
}
Print the list
/* The print queue */
void print(NODE* head) {
NODE* temp = head;
while (temp != NULL) {
std::cout << temp->data << std::endl;
temp = temp->next;
}
}
The complete code is as follows:
#include <iostream>
/* The node structure */
struct NODE
{
int data;
struct NODE* next;
};
/* Add elements - The pressure of stack */
void push(NODE** head, int dat) {
struct NODE* new_node = new NODE();
new_node->data = dat;
new_node->next = *head;
*head = new_node;
}
/* Add elements - add */
void add(NODE** head, int dat) {
struct NODE* new_node = new NODE();
new_node->data = dat;
new_node->next = NULL;
if (*head != NULL) {
struct NODE* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
}
else {
*head = new_node;
}
}
/* Inversion of the list */
void reverse(NODE** head) {
struct NODE* pre = NULL;
struct NODE* cur = *head;
struct NODE* nxt;
while (cur != NULL) {
// Reverse pointer
nxt = cur->next;
cur->next = pre;
// Move the cursor
pre = cur;
cur = nxt;
}
*head = pre;
}
/* Inversion of the list - Copy the original table to return the reverse table */
NODE* reverse(NODE* head) {
if (head == NULL || head->next == NULL) {
return head;
}
NODE* new_head = reverse(head->next);
// Reverse pointer
head->next->next = head;
head->next = NULL;
return new_head;
}
/* The print queue */
void print(NODE* head) {
NODE* temp = head;
while (temp != NULL) {
std::cout << temp->data << std::endl;
temp = temp->next;
}
}
int main() {
struct NODE* n = NULL;
add(&n, 1);
add(&n, 2);
add(&n, 3);
n = reverse(n);
print(n);
return 0;
}
I hope this article is helpful to you C++ programming.