Reversing linked list iteratively and recursively in C++
A) iteratively
1) need three pointers parent, cur and child
2) break the forward link: parent->next = NULL;
3) point cur->next =parent
4) move to next element for all three pointers
parent = cur;
cur = child;
child = child->next;
code:
struct Node* reverse_iterate(struct Node** head)
{
Node *parent = *head;
Node *cur = parent->next;
Node *child = cur->next;
/* break forward link */
parent->next = NULL;
while(child) {
cur->next = parent;
parent = cur;
cur = child;
child = child->next;
}
cur->next = parent;
*head = cur;
return *head;
}
B) recursively
code:
void reverse_recursion(struct Node*& cur )
{
if (cur==NULL) return;
Node* rest = cur->next;
if (rest==NULL) return;
reverse_recursion(rest);
cur->next->next = cur;
cur->next = NULL;
cur = rest;
}
Full code:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
// only for the 1st Node
void initNode(struct Node *head,int n){
head->data = n;
head->next =NULL;
}
// apending
void addNode(struct Node *head, int n) {
Node *newNode = new Node;
newNode->data = n;
newNode->next = NULL;
Node *cur = head;
while(cur) {
if(cur->next == NULL) {
cur->next = newNode;
return;
}
cur = cur->next;
}
}
/* reverse the list */
struct Node* reverse_iterate(struct Node** head)
{
Node *parent = *head;
Node *cur = parent->next;
Node *child = cur->next;
/* break forward link */
parent->next = NULL;
while(child) {
cur->next = parent;
parent = cur;
cur = child;
child = child->next;
}
cur->next = parent;
*head = cur;
return *head;
}
void reverse_recursion(struct Node*& cur )
{
if (cur==NULL) return;
Node* rest = cur->next;
if (rest==NULL) return;
reverse_recursion(rest);
cur->next->next = cur;
cur->next = NULL;
cur = rest;
}
void display(struct Node *head) {
Node *list = head;
while(list) {
cout << list->data << " ";
list = list->next;
}
cout << endl;
}
int main()
{
struct Node *head = new Node;
initNode(head,1);
addNode(head,2);
addNode(head,3);
addNode(head,4);
addNode(head,5);
display(head);
cout<<"Reverse the list iteratively"<<endl;
reverse_iterate(&head);
display(head);
cout<<"Reverse the list recursively"<<endl;
reverse_recursion(head);
display(head);
}
Running results
Process started >>>
1 2 3 4 5
Reverse the list iteratively
5 4 3 2 1
Reverse the list recursively
1 2 3 4 5
<<< Process finished.
Video: Reversing linked list iteratively and recursively in C++
Reversing the linked lists can be in two ways and are explained well in the following location. Anyways, thanks for posting such a useful content here and please keep sharing the information in the future.
ReplyDeleteReversing the Linked lists in Cpp