Create a reverse LinkedList in C++ from a given LinkedList

Question

I'm having some trouble create a linkedlist in reverse order from a given linkedlist.

I come from a java background, and just started doing some C++.

Can you check out my code and see what's wrong? I'm guessing I'm just manipulating pointer and not creating anything new.

//this is a method of linkedlist class, it creates a reverse linkedlist
//and prints it

void LinkedList::reversedLinkedList()
{
    Node* revHead;

    //check if the regular list is empty
    if(head == NULL)
       return;

    //else start reversing
    Node* current = head;
    while(current != NULL)
    {
        //check if it's the first one being added
        if(revHead == NULL)
           revHead = current;

        else
        {
            //just insert at the beginning
            Node* tempHead = revHead;
            current->next = tempHead;
            revHead = current;
        }
        current = current->next;

     }//end while

     //now print it
     cout << "Reversed LinkedList: " << endl;

     Node* temp = revHead;
     while(temp != NULL)
     {
         cout << temp->firstName << endl;
         cout << temp->lastName << endl;
         cout << endl;

         temp = temp->next;
      }

}//end method

Answer 1

Easier one: Go through your linked list, save the previous and the next node and just let the current node point at the previous one:

void LinkedList::reversedLinkedList()
{
    if(head == NULL) return;

    Node *prev = NULL, *current = NULL, *next = NULL;
    current = head;
    while(current != NULL){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    // now let the head point at the last node (prev)
    head = prev;
}

Answer 2

Node* revHead;
// ...
while(current != NULL)
{
    //check if it's the first one being added
    if(revHead == NULL)

You don't initialize revHead but you use it. (I hope it is already clear to you that revHead is a local variable used to store a memory address, and not something that exists outside the method/procedure)

The Storage Class of revHead is automatic (aka in the local scope-body). In C++ when you do a declaration like that, there is not guarantee that the value will be 0.

(unless the storage class is of type static or the variable is global where it is automatically initialized to 0 if no other value is provided. In your case the variable has storage class of type auto which means it is locally defined in a function, and when declaring a local variable, without specifying a value, the value is garbage. Keep in mind that with the next C++ Standard C++0x the keyword auto has a new meaning).

The value in your case is garbage which makes the if fail. See more Information here : Link

Do a

Node* revHead = NULL;

Keep in mind that maybe you may have errors like that in other part of your code as well.

Answer 3

This is done using just two temporary variables.

Node* list::rev(Node *first)
{
    Node *a = first, *b = first->next;
    while(a->next!=NULL)
    {
        b = a->next;
        a->next = a->next->next;
        b->next = first;
        first = b;
    }
    return first;
}

Also, you can do this using recursion.

Answer 4

Another method would be to first traverse the list and store all data in a stack,then create a new list and insert data in it from top of the stack.Stack being LIFO will give you the data in reverse order and hence you will have a reversed list.

Answer 5

NODE * ReverseLinkedList(NODE * head){
    if (head == NULL)
        return NULL;

    NODE * previous = NULL;
    while (head != NULL) {
        // Keep next node since we trash the next pointer.
        NODE *next = head->pNext;
        // Switch the next pointer to point backwards.
        head->pNext = previous;
        // Move both pointers forward.
        previous = head;
        head = next;
    }
    return previous;
}

Answer 6

I'm not sure, but I think you want a doubly linked list where the node has a next and previous. It will not work using an external pointer to the list. You will not have the address of the previous node.

If not use the method above with a stack it's a good suggestion.

Answer 7

The above is a reverse of Link List

void LinkList::rev()
{
    if(pFirst == NULL) return;

    ListElem *prev = NULL, *current = NULL, *next = NULL;
    current = pFirst;
    while(current != NULL)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    // now let the head point at the last node (prev)
    pFirst = prev;
}

Answer 8

The sample below use the recursion for reversing a linklist. I asked this Qs at a job interview. This has been tested and works. ListElem is the node.

void LinkList::reverse()
{
if(pFirst == NULL) return;
ListElem* current = pFirst;
revCur(NULL, current, NULL);
}

void LinkList::revCur(ListElem *prev, ListElem* current, ListElem* next)
{
 //   ListElem *prev = NULL, *current = NULL, *next = NULL;
 if ( current != NULL )
 {
     next = current->next;
     current->next = prev;
     prev = current;
     current = next;
     pFirst = prev;
     this->revCur(prev,current,next);
    }
}

Answer 9

  #include <stdint.h>
  /*
      this is a generic (structure agnostic) routine for reversing a singly linked list.
      1st argument is the memory address the structure is located at, and
      2nd argument is the memory address to this particular structure's NEXT member.
  */
  void *rsll(void *struct_address, void *next_address /*(void **)*/)
  {
    uint32_t offset, holder;
    offset = next_address - struct_address;

    void **p = struct_address, *progress = NULL;
    while(p)
    {
      void *b;
      holder = (uint32_t)p;
      holder += offset;
      p = (void**)holder; //&(N->next)
      b = *p; //(N->next)
      *p = progress; //(N->next)
      holder = (uint32_t)p;
      holder -= offset;
      p = (void**)holder; //N
      progress = p;
      p = b;
    }
    return progress;
  }

  #include <stdio.h>
  int
  main()
  {
    struct list_t
    {
      int integer;
      struct list_t *next;
    };
    struct list_t d = {40,NULL},
                  c = {30,&d},
                  b = {23,&c},
                  a = {10,&b};
    struct list_t *list;
    list = &a;
    list = rsll(list,&(list->next));
    while(list)
    {
      printf("%d\n",list->integer);
      list = list->next;
    }
    return 0;
  }

Answer 10

My fully executable solution for a reversed linked list using a class since most examples one finds are using just a struct:

#include <iostream>
#include <string>

class listElement
{
    std::string data;
    listElement* next;
    listElement* last; //for doubly linked list

    void append(std::string);
    void displayElements();
    void reverseDisplayElements(listElement*);

    listElement* reverseList(listElement*);


public:
    listElement() = default;
    listElement(std::string newElement)
        :data(newElement)
        , next(nullptr)
        , last(this)
    {}
    listElement &operator=(const listElement& other) = default;
    ~listElement();

    void setElement(std::string element){append(element);}
    void getElements();
    void getElementsReverse(listElement* elements);

    listElement* setElementsInReverseOrder(listElement* elements);
};

listElement::~listElement()
{
    //If the end is not reached, call the method again
    if (next != nullptr)
    {
        next->~listElement();
        delete(next);
    }
}

void listElement::getElements()
{
    std::cout << "\nPrint list:" << std::endl;
    displayElements();
}

void listElement::getElementsReverse(listElement *elements)
{
    std::cout << "\nJust print the list in reverse order:" << std::endl;
    reverseDisplayElements(elements);
}

listElement *listElement::setElementsInReverseOrder(listElement *elements)
{
    std::cout << "\n...Reversing elements..." << std::endl;
    return reverseList(elements);
}

void listElement::append(std::string newData)
{
    // Double linked list
    //    last->next = new listElement();
    //    last->next->data = newData;
    //    last->next->next = nullptr;
    //    last = last->next;

// Singly linked list
    //has next the value nullptr?
    //If yes, next pointer
    if (next == nullptr)
    {
        next = new listElement();
        next->data = newData;
        next->next = nullptr;
    }
    //else the method again
    else
        next->append(newData);
}

listElement* listElement::reverseList(listElement* head)
{
    //return if no element in list
    if(head == nullptr)
        return nullptr;

    //initialize temp
    listElement* temp{};

    while(head != nullptr){
        listElement* next = head->next;
        head->next = temp;
        temp = head;
        head = next;
    }
    return temp;
}

void listElement::displayElements()
{
    //cout the first entry
    std::cout << data << std::endl;
    //if the end is not reached, call method next again
    if (next != nullptr)
        next->displayElements();
}

void listElement::reverseDisplayElements(listElement*head)
{
    //recursiv from the last to the list beginning - stop
    listElement *temp = head;

    if(temp != nullptr)
    {
        if(temp->next != nullptr)
        {
            reverseDisplayElements(temp->next);
        }
      std::cout << temp->data << std::endl;
    }
}

int main ()
{
    //Pointer to the Beginning of the list
    listElement* linkedList = new listElement("Element 1");

    //add more elements
    linkedList->setElement("Element 2");
    linkedList->setElement("Element 3");
    linkedList->setElement("Element 4");

    linkedList->getElements();
    linkedList->getElementsReverse(linkedList);
    linkedList->getElements();
    linkedList = linkedList->setElementsInReverseOrder(linkedList);
    linkedList->getElements();

    return 0;
}

My recommendation for production code is using

the std::list since it is a linked list

or a std::vector if you need an efficient array implementation.