Example of the reverse order of C and C++ double linked list

Example of the reverse order of C/C++ double linked list

1. Node structure

The data structure of bidirectional linked list is defined as follows:

 typedef struct node
    {
      ElemType data;
      struct node *prior
      struct node *next;
    }list;

Where, ElemType can be any data type, such as int, float or char, etc. In the algorithm, it is specified as int type by default.

2. Lead node

This paper describes the reverse order of the two-way linked list. The reverse order of the linked list needs to maintain three Pointers, pointing to the previous node, the current node and the next node respectively. The specific code is as follows:

 list *reverselist(list *head)
    {
      if ((NULL == head) || (NULL == head->next))
      {
        return head;
      }
      list *p1=head->next, *p2=p1->next, *p3=NULL;
      p1->next = NULL;
      while (p2)
      {
        p3 = p2->next;      //  Save under the current node 1 node 
        p2->next = p1;      //  Change the current node next Field, pointing in front of it 1 A node 
        p1->prior = p2;     //  Before the change 1 A node prior Field, pointing to the back of it 1 A node 
        p1 = p2;         //  The pointer goes down 1 A node 
        p2 = p3;
      }
      head->next = p1;       //  Recovery header 
      p1->prior = head;
      return head;
    }

In the process of reverse order of linked list, it is very important to prevent the problem of broken chain. Therefore, when moving the pointer in reverse order of a node, it is necessary to use a pointer to point to the next node of that node to prevent the loss of the next node.

3. No leading node

 list *reverselist(list *head)
    {
      if ((NULL == head) || (NULL == head->next))
      {
        return head;
      }
      list *p1=head, *p2=p1->next, *p3=NULL;
      p1->next = NULL;
      while (p2)
      {
        p3 = p2->next;
        p2->next = p1;
        p1->prior = p2;
        p1 = p2;
        p2 = p3;
      }
      head = p1;
      return head;
    }

The difference between the reverse order of the list without the lead node and the lead node is the red code, that is, the initial p1 points to the first node instead of the head node, and the final head points directly to p1 instead of using its next to point to p1.

Thank you for reading, I hope to help you, thank you for your support of this site!