How to reverse linked list C++

Question

Possible Duplicate:
Reverse a singly linked list
reverse a linked list?

I have been trying to figure out how to displays the contents of a linked list of numbers in reverse order. I tried changing nodes around and i cant figure it out. its a singly linked list. I thought of implementing a stack. is there a simpler way? heres my code. i need the function to be in the header file, and it will be implemented in the main.cpp. ive been trying for hours today and yesterday and this is really a last resort. i have pages of notes of failed algorithms. as well as pages of google searches but nothing seems to work. if it makes a difference im using Microsoft Visual Studio 2010 (not my first choice). the code i presented does not have what ive been trying as it all failed horribly and usually produced errors.

#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H
#include <iostream>
#include <string>
#include <stack>

#include "Node.h"

using namespace std;
using namespace bruno;

namespace bruno
{
template< typename T>
class LinkedList
{
    private:        Node<T>  * head;
                    Node<T>  * tail;
                    int numberOfNodes;

    public:         LinkedList();
                    ~LinkedList();

                    int length(); 

                    Node<T>  * getHead() { return head; };
                    Node<T>  * getTail() { return tail; };

                    void insertInFront(T d);
                    void insertInBack(T d);

                    static void listContents( Node<T> * head);  

                    static T  sum( Node<T>  * head);    //     assume head is not NULL at call

                    static void  increment( Node<T>  * head, T val); 
                    static void reverseListContents( Node<T> * head, Node<T> * tail, int n );
};


   template< typename T >
   LinkedList<T>::LinkedList()
   {
       head = tail = NULL;
       numberOfNodes = 0;
   }


   template< typename T >
   LinkedList<T>::~LinkedList()
   {
   }



   template< typename T >
   int LinkedList<T>::length()
   { 
       return numberOfNodes; 
   }



   template< typename T >
   void LinkedList<T>::insertInFront(T d)
   {
        Node<T> * p =  new Node<T>;
        p->data  =  d;
        p->next  = head;
        head = p;
        if ( tail == NULL )
            tail = p;
        numberOfNodes++;
   }




   template< typename T >
   void LinkedList<T>::insertInBack(T d)
   {
        if ( tail == NULL )
            insertInFront(d);
        else {
                tail->next = new Node<T>;
                tail = tail->next;
                tail -> data = d;
                tail -> next = NULL;
        }
        numberOfNodes++;

   }


   template< typename T >                       
   void LinkedList<T>::listContents(Node<T> * head)
   {
        if (head == NULL)  return;
        else
        {      cout <<  head->data  << "  ->  ";
               listContents( head -> next );
        }
   }




   template< typename T >                       
   T LinkedList<T>::sum(Node<T> * head)
   {
        if ( (head->next) == NULL )  return  head->data;
        else
             return  ( head->data    +   sum( head->next ) );
   }




   template< typename T >                       
   void LinkedList<T>::increment(Node<T> * head, T  val)
   {
        if ( head == NULL )  return;
        else
        {
            head->data += val;                    // add val to current data value
            increment( head->next, val );
        }

   }

   template< typename T >
   void LinkedList<T>::reverseListContents (Node<T> * head, Node<T> * tail, int n)
   {
       //clueless!


   }



}

#endif

you don't need a stack. you can do it in-place. try to google "reverse singly linked list in place" — K Mehta, Mar 10 '12 at 05:06
If this is homework, please add the `homework` tag. Without the `homework` tag, you'll get a bunch of irrelevant answers. — Emile Cormier, Mar 10 '12 at 05:07
Welcome to StackOverflow. Please use the search (or google) before posting new questions; many have already been asked and answered. — Brian Roach, Mar 10 '12 at 05:08
If this *isn't* homework, don't write your own list data structure. Use `std:list`. — Robᵩ, Mar 10 '12 at 05:11
^^^ "Don't to that, use `std::xxx`" are the answers you typically get when you neglect to include the `homework` tag. :-) — Emile Cormier, Mar 10 '12 at 05:14
possible duplicate of [reverse a linked list?](http://stackoverflow.com/q/2887600/), [Create a reverse LinkedList in C++ from a given LinkedList](http://stackoverflow.com/q/4908193/90527). — outis, Mar 10 '12 at 13:39
if you read the full question i state i have searched google as well as this exact website and all the algorithms i have found doing such are not as easily implemented. yes this is homework. — user1260607, Mar 10 '12 at 20:49
whoever closed this is stupid.. different code calls for different solution, yeah im trying to do the same thing as some other questions, but its all subjective and those dont work for me cuz guess what? im not writing the same exact code as they are.. — user1260607, Mar 10 '12 at 21:25

score 1 · Accepted Answer · answered Mar 10 '12 at 06:42

1

You can do it this way:

1) Find the last node and print it.

2) Traverse the linked list to find the node that has the node you last printed as its next node, and print it.

3) Go to step 2 until there are no more nodes to print.

answered Mar 10 '12 at 06:42

David Schwartz

179,497
17
214
278

great algorithm! thank you for that. much more help then people posting code and not explaining, or code that doesnt actually do what i want. – user1260607 Mar 10 '12 at 22:02

score 0 · Answer 2 · answered Mar 10 '12 at 05:11

Recursive solution should do

Node * Reverse( Node * ptr , Node * previous)
{
    Node * temp;
    if(ptr->next == NULL) {
        ptr->next = previous;
        return ptr;
    } else {
        temp = Reverse(ptr->next, ptr);
        ptr->next = previous;
        return temp;
    }
}

usage:

ReversedList = Reverse(head, NULL);

Usually you can treat your Node class as a Linked list, you don't need a separate class.

score 0 · Answer 3 · answered Mar 10 '12 at 05:31

There are two general ways to reverse a singly linked list.

One is to change the pointers so that the tail node becomes the head node and vice versa, and all the pointers in between go the other way. Each data item stays in the same node as before.

The other approach is to keep the structure of the nodes intact, but move the data.

Because you named your function reverseListContents, I suspect you are trying to do the latter. This is harder to do.

Reversing the structure of the list (first approach) can be done with a simple loop.

Have you ever seen someone flip a chain of overlapping playing cards, laid on a table, by flipping the last one? That's similar to how the pointers change direction.

Watch this YouTube video very carefully and implement the same thing in C++:

http://www.youtube.com/watch?v=yW1Ch7eo4g4

Don't forget to update your head and tail pointers, which exchange nodes.

that first method would work, if this wasnt a singly linked list... — user1260607, Mar 10 '12 at 21:34

score 0 · Answer 4 · answered Mar 10 '12 at 06:22

I won't write detail code for you but will give pseudo-code:

void printLinkedListReverseOrder(NodeType * ptr)
{
    // Be defensive, Don't assume proper input. Validate it first
    if(NULL == ptr) return;

    // If this node is not the last, print it's next node first
    if(NULL != ptr->next) printLinkedListReverseOrder(ptr->next);

    // When all nodes after it is printed, then print the node itself
    print(ptr);
}

Note that this uses recursion, which isn't good for a big linked list. If you have a big linked list and want to use loop, then you may use a stack to store the nodes before printing them.

How to reverse linked list C++

4 Answers4