# 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

Move pointer:

Reverse the pointer to the list element 1 by 1, starting at the head of the list with 3 Pointers

Recursive:

Recursively, the end of the list is found and the pointer is reversed 1 by 1

Algorithm implementation:

``````
/*  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;
}
struct NODE* new_node = new NODE();
new_node->data = dat;
new_node->next = NULL;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
}
else {
}
}

``````

Move the cursor

``````
/*  Inversion of the list  */
struct NODE* pre = NULL;
struct NODE* nxt;
while (cur != NULL) {
//  Reverse pointer
nxt = cur->next;
cur->next = pre;
//  Move the cursor
pre = cur;
cur = nxt;
}
}

``````

recursive

``````
/*  Inversion of the list - Copy the original table to return the reverse table  */
}
//  Reverse pointer
}

``````

Print the list

``````
/*  The print queue  */
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;
}
struct NODE* new_node = new NODE();
new_node->data = dat;
new_node->next = NULL;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
}
else {
}
}
/*  Inversion of the list  */
struct NODE* pre = NULL;
struct NODE* nxt;
while (cur != NULL) {
//  Reverse pointer
nxt = cur->next;
cur->next = pre;
//  Move the cursor
pre = cur;
cur = nxt;
}
}
/*  Inversion of the list - Copy the original table to return the reverse table  */
}
//  Reverse pointer
}
/*  The print queue  */
while (temp != NULL) {
std::cout << temp->data << std::endl;
temp = temp->next;
}
}
int main() {
struct NODE* n = NULL;