Reverse Linked List

[ct180]

I am trying to a write a member function that will reverse a linked list. However, I recieve a constant neverending print of 2's that I have to manually terminate when I try to print.

The member function is as follows:

  void Node::reverse()
{

    Node *pos = this, *prev = NULL, *next = NULL;
    while(pos != NULL){
        next = pos->next;
        pos->next = prev;
        prev = pos;
        pos = next;
    }
    pos = prev;
}

[kevinkjt2000]

This is not enough code to determine why you see a constant never ending print of 2's.
A linked list uses a head node (sometimes called a root node) to keep track of the start of the linked list. Are you updating this root node after calling Node::reverse?

[ct180]

I also have a main source that I am pushing it through:

#include "Node.h"
#include "DNode.h"
#include <iostream>

int main() {
  Node *head = new Node();
  head->key = 2;
  head->add(3);
  head->add(5);
  head->add(7);
  head->print();

  head->reverse();
  head->print();

The header file with the node class is here:

#ifndef NODE_H
#define NODE_H

class Node {

  public:

    int key;
    Node *next;

    void add(int key);
    void print();
    void reverse();

};

#endif 

[kevinkjt2000]

Again this is not enough code to show the error, but already I see that you are not implementing a linked list in the traditional object oriented way.
Usually there is a LinkedList class that holds the Node class and head Node privately.
So functions like add, print, and reverse would belong to LinkedList. A constructor for Node would be handy in initializing stuff like next to NULL and providing a key. Object oriented programming encourages making each class responsible for only the things it needs to be responsible for.

Does your print method stop on NULL?
Does your add method initialize the new Node's next to NULL?

[ct180]

Sorry, Im not sure what else to add. This is part of an assignment and the class and its use were prefined from what I have posted. I was under the impression that using a member function for head and assigning *pos = this would assign where it needs to start/the head? I;m drawing from the usage of the other functions, which work fine.


Additionally, this is the rest of the soure for the functions:

#include <iostream>
#include "Node.h"

void Node::add(int key) {
  Node *pos = this;
  while (pos->next != NULL)
    pos = pos->next;
  pos->next = new Node;
  pos       = pos->next;
  pos->key  = key;
  pos->next = NULL;
}

void Node::print() {
  Node *pos = this;
  while (pos != NULL) {
    std::cout << pos->key << " ";
    pos = pos->next;
  }
  std::cout << std::endl;
}

void Node::reverse() {

  Node *left, *head = this, *right, *mid;

  while(head != NULL){
   mid->next=left;
   left=mid;
   mid=right;
   right=right->next;
  } 
  head=mid;
}

[kevinkjt2000]

When your first node is created head->next is not set to NULL, although I'm not certain this is what is causing your problem. This is one good reason to create a constructor for the Node class.
When head is reversed in main, how does main know what the new head node is? This is a good reason to encapsulate Nodes in a LinkedList class, so that main just reverses and prints on a list instead of a node.

[ct180]

Ok, thanks for the advice! I managed to get it working after realizing that the function had to be defined as a Node *Node::reverse() and not a void *Node() reverse and setting the int main operation to be head = head->reverse();