C++ linked list in reverse order

  • 2020-04-02 02:41:38
  • OfStack

In this paper, an example is given to demonstrate the method of reverse order of linked list in C++. Specific methods are as follows:

First, the difficulty with C++ linked lists in reverse order is how to modify them one by one. It's not an array, but the general idea is the same, so you can use a for sequence, a cursor for the I in the for loop, just remember the previous node and the next node, especially the last node, because you can't access the next one after modification, so you want to record. For each loop only changes the pointer to the node to which it is pointing, so that there is no confusion.

A for loop is easy to understand. The example code is as follows:


#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

//Linked list node class
class Node
{
private:
  int m_data;
  Node* m_next;

  Node(Node&) {}    //copy constructor is not allowed

public:
  explicit Node(int val = 0) : m_data(val), m_next(NULL) {}
  int getData() const { return m_data; }
  void setData(int val) { m_data = val; }
  Node* getNext(void) const { return m_next; }
  void setNext(Node* p) { m_next = p; }
};

//The list
class MyList
{
private:
  Node* m_head;  //pionter to the first node of the list
  Node* m_tail;  //poinoer to the last node of the list

  MyList(MyList&) {}
public:
  explicit MyList() : m_head(NULL), m_tail(NULL) {}
  void addNode(Node* pNode);
  void show(void) const;
  void reverse(void);
  void clean(void);
};

void MyList::addNode(Node* pNode)
{
  if (m_head)
  {
    m_tail->setNext(pNode);
    m_tail = pNode;
  }
  else    //blank list
  {
    m_head = pNode;
    m_tail = pNode;
  }
}

void MyList::show(void) const
{
  Node* pNode = m_head;
  while (pNode)
  {
    std::cout << pNode->getData() << "  ";
    pNode = pNode->getNext();
  }
}

void MyList::reverse(void)
{
  Node* preNode = NULL;    //The previous of the following cursor
  Node* pNode ;    //Points to each node, which is equivalent to a cursor
  Node* afterNode;    //The previous of the above cursor

  for (pNode = m_head; pNode != NULL; pNode = afterNode)  //Each loop here corresponds to one node, which is essentially the same as an array
  {
    afterNode = pNode->getNext();
    pNode->setNext(preNode);
    preNode = pNode;
  }

  pNode = m_head;  //Swap the header and tail Pointers
  m_head = m_tail;
  m_tail = pNode;
}

void MyList::clean(void)
{
  if (m_head)
  {
    Node* pNode = m_head;
    Node* pTemp;
    while (pNode)
    {
      pTemp = pNode->getNext();
      delete pNode;
      pNode = pTemp;
    }

    m_head = m_tail = NULL;
  }
}

int main(void)
{
  MyList listHead;

  srand((unsigned)time(NULL));
  for (int i = 0; i < 9; i++)
  {
    int temp = rand() % 50;
    Node* pNode = new Node(temp);
    listHead.addNode(pNode);
  }
  listHead.show();

  listHead.reverse();
  cout << endl;
  listHead.show();
  listHead.clean();
  listHead.show();
  
  system("pause");
}

I believe that the example of this paper for everyone to learn C++ data structure and algorithm can play a certain reference.


Related articles: