C++ data structures and algorithms for determining whether a linked list is a palindrome structure

The example of this article describes the method of C++ to determine whether a linked list is a palindrome structure. I will share it with you for your reference as follows:

Topic:

Given 1 chain header node head, determine if it is palindromic

Such as:

1- > 2- > 1 true
1- > 2- > 2- > 1 true
1- > 2- > 3- > 4- > 2- > 1 false

Problem solving ideas and code

1. Find the middle node of the linked list and put all the nodes to the right of the middle node of the linked list into one stack.

2. Then compare the node at the beginning of the list with the element at the top of the stack. If it is not equal, return false will be found.

Algorithm C++ code:

List node structure definition

typedef struct Node
{
  int data;
  struct Node* next;
}node, *pLinkedList;

bool isHuiWen(pLinkedList head)
{
  if (head == NULL || head->next == NULL)
    return true;
  pLinkedList right = head->next;// Save the bottom of the middle node 1 A node ( If it is even, it is the middle node to the right )
  pLinkedList cur = head;      // Quick pointer 
  while (cur->next != NULL && cur->next->next != NULL)
  {
    right = right->next;
    cur = cur->next->next;
  }
  // When the number of points in the linked list is odd: 
  if (cur->next != NULL && cur->next->next == NULL)
    right = right->next;
  // Place the nodes on the right side of the list 1 A stack of 
  stack<pLinkedList>* s = new stack<pLinkedList>();
  while (right != NULL)
  {
    s->push(right);
    right = right->next;
  }
  // Compare the left and right sides of the list for equality 
  while (!s->empty())
  {
    if (head->next->data != s->top()->data)
      return false;
    s->pop();
    head = head->next;
  }
  return true;
}

I hope this article is helpful to you C++ programming.