Tuesday, July 10, 2012

Write a program to construct and reverse a linked list

We write an iterative approach to reverse a linked list. The approach is to start from the head node and prep-end the subsequent nodes so that the list gets reversed. 3 pointers are used to do the list manipulation.

C++ program to reverse a linked list

#include <iostream>
using namespace std;

// List nodeclass
class Node {
public:
    int data;
    Node* next;
};

// Linked list class
class List {
public:
    List() { head = NULL; }
    ~List() {}
    void addNode(int val);
    void reverse();
    void print();

private:
    Node* head;
};

// Function to add a node to the list
void List::addNode(int val)
{
    Node* temp = new Node();
    temp->data = val;
    temp->next = NULL;

    if ( head == NULL ) {
        head = temp;
    }
    else {
        Node* temp1 = head;
        while ( temp1->next != NULL )
            temp1 = temp1->next;
        temp1->next = temp;
    }
}

// Iterative function to reverse a list
void List::reverse()
{
    Node* n1 = head;
    Node* n2 = NULL;
    Node* n3 = NULL;
    while ( n1 != NULL )
    {
        head = n1;
        n2 = n1->next;
        n1->next = n3;
        n3 = n1;
        n1 = n2;
    }
}

void List::print()
{
    Node* temp = head;
    while ( temp != NULL ) {
        cout << temp->data << " ";         
        temp = temp->next;
    }
    cout << endl; 
} 

// Test program 
int main() {    
    List* list = new List();     
    list->addNode(100);
    list->addNode(200);
    list->addNode(300);
    list->addNode(400);
    list->addNode(500);
    list->print();
    list->reverse();
    list->print();
    delete list;
}


Output:-
100 200 300 400 500
500 400 300 200 100

3 comments :

  1. I am loving to read your posts. Also I've come up with some naming convention which helps me visualize what's goin on instead of using n1, n2 and n3 as names. Here is exactly same code with different naming. Let me know how do you like it?

    File linklist.h

    #ifndef _LINK_LIST_H_
    #define _LINK_LIST_H_

    class Node {
    public:
    int data;
    Node * next;
    };

    class List {
    public:
    List() { head = NULL; }
    ~List();
    void add_node(int val);
    void reverse();
    void print();
    private:
    Node *head;
    };
    #endif


    File: linklist.cpp

    #include
    #include "linklist.h"
    using namespace std;

    List::
    ~List() {
    Node *curr_link = head;
    while (curr_link != NULL) {
    Node * tmp_link = curr_link->next;
    delete curr_link;
    curr_link = tmp_link;
    }
    }

    void
    List::add_node(int val) {
    Node *temp = new Node();
    temp->data = val;
    temp->next = NULL;

    if (head == NULL) {
    head = temp;
    } else {
    Node *curr_link = head;
    while ( curr_link->next != NULL)
    curr_link = curr_link->next;
    curr_link->next = temp;
    }
    }

    // iterative function to reverse a list
    void
    List::reverse() {
    Node *curr_link = head;
    Node *next_link = NULL;
    Node *back_link = NULL;

    while (curr_link != NULL) {
    head = curr_link;
    next_link = curr_link->next;
    curr_link->next = back_link;
    back_link = curr_link;
    curr_link = next_link;
    }
    }

    void
    List::print() {
    Node *curr_link = head;
    while (curr_link != NULL) {
    cout <data <next;
    }
    cout << endl;
    }


    File: linktest.cpp

    #include
    #include "linklist.h"
    using namespace std;

    List::
    ~List() {
    Node *curr_link = head;
    while (curr_link != NULL) {
    Node * tmp_link = curr_link->next;
    delete curr_link;
    curr_link = tmp_link;
    }
    }

    void
    List::add_node(int val) {
    Node *temp = new Node();
    temp->data = val;
    temp->next = NULL;

    if (head == NULL) {
    head = temp;
    } else {
    Node *curr_link = head;
    while ( curr_link->next != NULL)
    curr_link = curr_link->next;
    curr_link->next = temp;
    }
    }

    // iterative function to reverse a list
    void
    List::reverse() {
    Node *curr_link = head;
    Node *next_link = NULL;
    Node *back_link = NULL;

    while (curr_link != NULL) {
    head = curr_link;
    next_link = curr_link->next;
    curr_link->next = back_link;
    back_link = curr_link;
    curr_link = next_link;
    }
    }

    void
    List::print() {
    Node *curr_link = head;
    while (curr_link != NULL) {
    cout <data <next;
    }
    cout << endl;
    }


    g++ linktest.cpp linklist.cpp

    Output:
    List: -10 10 20 -5
    Reversed list: -5 20 10 -10

    ReplyDelete
  2. Good points all aronud. Truly appreciated.

    ReplyDelete
  3. can you explain that reverse function. I don't quite get the while statement.

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top