Note 1

Take Note:

Take a note while surfing.





Note With Ink

Give your Note a Colorful Tag.




Easy to Access

Stay on same information and in Sync wherever you are.

Note 2

Take Note:

Organize your information,It may take Shape.





Think With Ink

Differ your Content by Color.




Easy to Access

Easy to pull up your content from anywhere anytime.

Note 3

Take Note:

Don't Let information to miss,Because it take shape





Note With Ink

Simple an Easy Way to take a note.




Easy to Access

Get the same in next visit.

Program Discussion :: Linked List
Home > Programs > Linked List

2. Write a program to reverse the single linked list

Answer:

#include <iostream>
#include <cstddef>
/* definition of the list node class */
class Node
{
    friend class LinkedList;
private:
    int _value; /* data, can be any data type, but use integer for easiness */
    Node *_pNext; /* pointer to the next node */    
public:
    /* Constructors with No Arguments */
    Node(void)
    : _pNext(NULL)
    { }    
    /* Constructors with a given value */
    Node(int val)
    : _value(val), _pNext(NULL)
    { }    
    /* Constructors with a given value and a link of the next node */
    Node(int val, Node* next)
    : _value(val), _pNext(next)
    {}    
    /* Getters */
    int getValue(void)
    { return _value; }    
    Node* getNext(void)
    { return _pNext; }
    };
/* definition of the linked list class */
class LinkedList
{
private:
    /* pointer of head node */
    Node *_pHead;
    /* pointer of tail node */
    Node *_pTail;
    
public:
    /* Constructors with a given value of a list node */
    LinkedList(int val);
    /* Destructor */
    ~LinkedList(void);
    
    /* Function to a};

/* definition of the linked list class */
class LinkedList
{
private:
    /* pointer of head node */
    Node *_pHead;
    /* pointer of tail node */
    Node *_pTail;
    
public:ppend a node to the end of a linked list */
    void tailAppend(int val);
    /* Function to reverse the list */
    void reverse();
    
    /* Traversing the list and printing the value of each node */
    void traverse_and_print();
};

LinkedList::LinkedList(int val)
{
    /* Create a new node, acting as both the head and tail node */
    _pHead = new Node(val);
    _pTail = _pHead;
}

LinkedList::~LinkedList()
{
    /*
     * Leave it empty temporarily.
     * It will be described in detail in the example "How to delete a linkedlist".
     */
}

void LinkedList::tailAppend(int val)
{
    /* The list is empty? */
    if (_pHead == NULL) {
        /* the same to create a new list with a given value */
        _pTail = _pHead = new Node(val);
    }
    else
     {
        /* Append the new node to the tail */
        _pTail->_pNext = new Node(val);
        /* Update the tail pointer */
        _pTail = _pTail->_pNext;
    }
}

void LinkedList::reverse()
{
    Node *pTempHead = _pHead, *pRestNodes = NULL, *pNextNode = NULL;
    /* The list is empty? do nothing */
    if (_pHead == NULL)
        return;
    /* The previous head node will act as the tail node after reversing */
    _pTail = _pHead;
    /* Take out the head node and make the reverse list basing on it */
    pRestNodes = _pHead->_pNext;
    
    while (pRestNodes != NULL) {
        /* Step1: Take out the next node */
        pNextNode = pRestNodes;
        /* Step2: Update the pointer of rest nodes after taking out the first */
        pRestNodes = pRestNodes->_pNext;
        /* Step3: Add the taken out node to the new list */
        pNextNode->_pNext = pTempHead;
        /* Step4: Update the new temp head node */
        pTempHead = pNextNode;
        /* Repeat Step 1-4 */
    }
    _pHead = pTempHead;
    _pTail->_pNext = NULL;
}

void LinkedList::traverse_and_print()
{
    Node *p = _pHead;    
    /* The list is empty? */
    if (_pHead == NULL) {
        cout << "The list is empty" << endl;
        return;
    }    
    cout << "LinkedList: ";
    /* A basic way of traversing a linked list */
    while (p != NULL) { /* while there are some more nodes left */
        /* output the value */
        cout << p->_value << " ";
        /* The pointer moves along to the next one */
        p = p->_pNext;
    }
    cout << endl;
}
int main(int argc, const char * argv[])
{
    /* Create a list with only one node */
    LinkedList list(1);
    /* Append 3 nodes to the end of the list */
    list.tailAppend(2);
    list.tailAppend(3);
    list.tailAppend(4);    
    cout << "Before reversing:" << endl;
    getch();
    }

Post Your Answer Here:

Name *
Email

Language:

Post Your Reply Here:



Language:

Post Your Reply Here: