reversing the linked list

Question

#include<iostream>
using namespace std;

struct node{
    int data;
    node* next;
};

node *head=NULL;

void print(struct node*)
{
    node *temp=head;
    while(temp!=NULL)
    {
        cout<<temp->data;
        temp=temp->next;
    }
}

struct node* insert(struct node* head,int x)
{
    node *temp=new node();
    temp->data=x;
    temp->next=head;
    head=temp;
    return head;
}

struct node* reverse(struct node* head)
{
    node *current,*next,*prev;
    current=head;
    prev=NULL;
    next=NULL;
    while(current!=NULL)
    {
        next=current->next;
        current->next=prev;
        current=next;
        prev=current;
    }
    head=prev;
    return head;
}

int main()
{
    struct node *head=NULL;
    head=insert(head,2);
    head=insert(head,4);
    head=insert(head,3);
    head=insert(head,8);
    print(head);
    head=reverse(head);
    print(head);
    return 0;

}

Can someone point out what is wrong with this code.I have tried executing it but I seem to be having a problem with printing. And even after I try making correction, it is only printing the linked list and not the reverse linked list. I am a beginner.Thank you.

Answer 1

Problem:

Your code has many things to fix, but pointing specifically to your question the problem is in the print function.

There are 2 problems for your question:

1. You're using a global variable called head that is always NULL instead of using the one that is passed as parameter.
2. Reverse function is incorrect.

Solution

Change this

node *head=NULL;

void print(struct node*)
{
    node *temp=head;
    while(temp!=NULL)
    {
        cout<<temp->data;
        temp=temp->next;
    }
}

For this:

void print(struct node* head)
{
    node *temp=head;
    while(temp!=NULL)
    {
        cout<<temp->data;
        temp=temp->next;
    }
}

In this way you will be using the node in the parameter instead of the node in global scope that is always NULL.

In reverse function change:

current = next;
prev = current;

For this:

prev = current;
current = next;

Additional information:

1. using namespace std; is a bad practice (More info here).
2. You should probably add a class to wrap the linked list with the methods.
3. I would use nullptr instead of NULL to avoid confusions (More info here).
4. Maybe you should search a good C++ textbook.

Full code:

#include<iostream>

struct node{
public:
    int data;
    node* next;
};

class linkedList
{
private:
    node* head;
public:
    linkedList();
    void print();
    void reverse();
    void insert(int);
    void invert();
};

linkedList::linkedList()
{
    head = nullptr;
}

void linkedList::print()
{
    node *temp = this->head;
    while(temp!=nullptr)
    {
        std::cout << temp->data;
        temp = temp->next;
    }
}

void linkedList::insert(int x)
{
    node *temp = new node();
    temp->data = x;
    temp->next = this->head;
    this->head = temp;
}

void linkedList::reverse()
{
    node *current,*next,*prev;
    current = this->head;
    prev = nullptr;
    next = nullptr;
    while(current != nullptr)
    {
        next = current->next;
        current->next=prev;
        prev = current;
        current = next;
    }
    this->head = prev;
}

int main()
{
    linkedList myList;
    myList.insert(4);
    myList.insert(4);
    myList.insert(3);
    myList.insert(8);
    myList.print();
    myList.reverse();
    myList.print();
    return 0;
}

Answer 2

Fix your print as others have mentioned.

Your reverse is incorrect.

In reverse, you have:

current = next;
prev = current;

prev will be NULL on the first iteration [which is correct]. But, afterwards, it won't be the previous node, but, just the same as the current node.

You want:

prev = current;
current = next;

Answer 3

My answer is less of a direct answer to what's plaguing your code and more of a look at what a "proper" C++ solution could look like. It utilizes a doubly-linked list, meaning the Nodes know what previous AND next Nodes in the list are. I did this because a function like reverse() becomes exponentially easier.

Tangent
Students are often given the option of writing a doubly linked list and skip it, not realizing how much easier it makes their lives, and the only cost is a few more pointer assignments. That's my class, anyway.
/Tangent

C++ is its own language from C. That becomes the case more and more every time a new C++ standard is released. This C method with a global Node and free functions is just horrible C++.

Below is an example of how a C++ linked list could look. This is quick code and shouldn't be considered definitive at all. I use a class, and encapsulate everything about a linked list into that class. I have some comments explaining some code choices (or lack thereof).

I chose not to use smart pointers, because to me they don't make a lot of sense in a data structure. That's a very subjective opinion.

I am also not taking advantage of any C++20 features; I just don't know them well enough yet.

#include <algorithm>
#include <iostream>

// Ideally all of this linked list code would be in its own header file that
// you include in your main.cpp
template <typename T>
class LinkedList;

template <typename T>
void print(LinkedList<T>& list);

template <typename T>
class LinkedList {
 public:
  LinkedList() = default;
  ~LinkedList();

  // I am ommitting the remainder of the Rule of 0/3/5 functions which are
  // required if you want the list to function properly. It is much simpler
  // to implment them using the copy/swap idiom
  // https://stackoverflow.com/a/3279550/6119582

  void push_back(T val);  // for C++ insert() usually means at any position
  void reverse();

  // Added for simplicity. The real way would be to ensure T can be printed
  // (operator<<() for custom T) and provide iterators for the LinkedList.
  // Worth noting that because I didn't want to implement the full Rule of
  // 0/3/5, that this function is less than ideal, but it exists only to
  // demonstrate that the list is behaving.
  friend void print<T>(LinkedList& list);

 private:
  struct Node {
    T data;
    Node* next = nullptr;
    Node* prev = nullptr;
  };

  Node* m_head = nullptr;
  Node* m_tail = nullptr;
};

template <typename T>
LinkedList<T>::~LinkedList() {
  Node* tmp = m_head;
  while (tmp) {
    m_head = m_head->next;
    delete tmp;
    tmp = m_head;
  }
  m_tail = nullptr;
}

template <typename T>
void LinkedList<T>::push_back(T val) {
  // Empty list
  if (!m_head) {
    m_head = new Node{val};
    m_tail = m_head;
    return;
  }

  m_tail->next = new Node{val};
  m_tail->next->prev = m_tail;
  m_tail = m_tail->next;
}

template <typename T>
void LinkedList<T>::reverse() {
  // We start at the end of the list, and simply swap the next and prev
  // pointers. And we do that for every Node in the list, finally, we swap the
  // LinkedList's head and tail pointers. This is a lot tougher in a singly-
  // linked list.
  Node* walker = m_tail;
  while (walker) {
    std::swap(walker->next, walker->prev);
    walker = walker->next;
  }
  std::swap(m_head, m_tail);
}

template <typename T>
void print(LinkedList<T>& list) {
  typename LinkedList<T>::Node* tmp = list.m_head;
  while (tmp) {
    std::cout << tmp->data << ' ';
    tmp = tmp->next;
  }
  std::cout << '\n';
}

int main() {
  LinkedList<int> list;

  for (int i = 1; i < 11; ++i) {
    list.push_back(i);
  }
  print(list);
  list.reverse();
  print(list);
}

Output:

1 2 3 4 5 6 7 8 9 10 
10 9 8 7 6 5 4 3 2 1

As you can see, actually writing C++ for a linked list is very different from writing a linked list in C. It's unfortunate that your class has not evolved in at least a decade.

It's also worth saying that if the class were to be fully implemented (iterators and other stuff I said was missing), the main function would look so much better and allow our list to be used by more of the Standard Library.