Sunday, April 20, 2014

Reversing linked list iteratively and recursively in C++



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++


1 comment:

  1. 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.

    Reversing the Linked lists in Cpp

    ReplyDelete