The following code creates a linked list with 20 random elements, and then reverses the list.

/*
reverse-linked-list.cpp
Jason B. Hill (jason@jasonbhill.com)
reverse a linked list in C++
*/
 
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
// Node class
class Node {
 
    public:
    int         data;
    Node*       next;
 
    // create a new node
    Node(int x, Node* addr) {
        data = x;
        next = addr;
    }
};
 
// LinkedList class
class LinkedList {
    private:
    Node*       head;
 
    public:
 
    // initialize a linked list with a NULL head
    LinkedList() {
        head = NULL;
    }
 
    // determine if a list is empty
    bool is_empty() {
        if(head == NULL) return 1;
        else return 0;
    }
 
    // add an item to a linked list
    void node_add(int val) {
        if(head == NULL) head = new Node(val, NULL);
        else {
            Node* n = head;
            while(n->next != NULL) n = n->next;
            n->next = new Node(val, NULL);
        }
    }
 
    // return the length of a linked list
    unsigned int length() {
        if(head == NULL) return 0;
        if(head->next == NULL) return 1;
        unsigned int len = 1;
        Node* n = head;
        while(n->next != NULL) {
            n = n->next;
            len++;
        }
        return len;
    }
 
    // print a linked list
    void print() {
        cout<<"[";
        if(head != NULL) {
            if(head->next == NULL) cout<<head->data;
            else {
                Node* n = head;
                while(n->next != NULL) {
                    cout<<n->data<<",";
                    n = n->next;
                }
                cout<<n->data;
            }
        }
        cout<<"]\n";
    }
 
    //reverse a linked list
    void reverse() {
        if(head != NULL and head->next != NULL) {
            Node* m = head;
            Node* n = head->next;
            Node* t = NULL;
            if(n->next != NULL) t = n->next;
            head->next = NULL;
            while(t->next != NULL) {
                n->next = m;
                m = n;
                n = t;
                t = t->next;
            }
            n->next = m;
            head = t;
            t->next = n;
        }
    }
};
 
int main(void){
 
    LinkedList      L;
    unsigned int    i;
 
    srand(time(NULL)); 
    for(i=0;i<20;i++) L.node_add(rand() % 100);
 
    L.print();
 
    L.reverse();
 
    L.print();
 
 
    return(0);
}

This can be compiled (using gcc/g++) using:

g++ reverse-linked-list.cpp -o reverse-linked-list

An example execution is:

$ ./reverse-linked-list 
[99,31,17,41,7,38,59,7,67,75,75,13,62,70,0,20,46,3,14,24]
[24,14,3,46,20,0,70,62,13,75,75,67,7,59,38,7,41,17,31,99]
Posted in C++
Share this post, let the world know

2 Comments

  1. asas
    Posted July 21, 2013 at 01:15 | Permalink

    [Error] ‘time’ was not declared in this scope

    What i do Now??

  2. jason
    Posted July 25, 2013 at 18:53 | Permalink

    Try using an include for time.h in the header.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">