Detailed explanation of single chain reversal using recursion and non-recursion

This article describes how to achieve single-chain inversion using recursion and non-recursion. There may be many students who don’t know much about what single-chain inversion is, so let’s cut the nonsense and go directly Read this article!
The question gives hints that both recursive and iterative algorithms can be used.
Because I don’t have a deep understanding of recursion, I first use iteration to write the algorithm. The head node in the question is considered to be the first node containing data
Question idea: start from the head node, traverse backward, and follow the order The reversal of the chains between nodes is gradually realized one by one.
First try to use 2 pointers to complete the operation, but fail

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
ListNode* pre = NULL;
  while(head -> next)
  {
 pre = head;
 head = head -> next;
 head -> next = pre; 
  }
  return head;
};

The reason is as follows: During the reversal process, head ->next has been reversed and cannot continue to After traversing, so adding a pointer and using 3 pointers to complete the operation

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
ListNode* pre = NULL;
  while(head)
  {
 ListNode* next = head -> next;
 head -> next = pre;//head是尾结点，指针置空
 head = next;
 pre = head; 
  }
  return pre;           //head = NULL
};

recursion will not happen. Please refer to Discuss to understand.
The idea is as follows: through recursion, the head node is continuously traversed backwards until the termination condition: stops after reaching the tail node.
The code is as follows:

class Solution {
public:       
ListNode* reverseList(ListNode* head) { 
//终止条件，达到尾结点停止
if(head == NULL || head ==NULL)
return head;
else
{
//头结点向后移动
ListNode* temp = reverList(head->next);
head->next->next = head;   //1
head->next = NULL;         //2
}
return temp;
};

The status presented when the recursive termination condition is reached is as follows:




The status after returning to the previous level of recursion is as follows:


AfterCommentsAfter the two lines of code 1 and 2, the status is as follows


It can be seen that the position of the head node is related to the number of recursion levels, and temp is The position of the reversed head node never moves, thus achieving the reversal effect.
Although I can understand the recursive code, I don't know how to design it yet, and I am still a novice.

##Related articles:

PHP implementation Single chainTable flip operation example

The above is the detailed content of Detailed explanation of single chain reversal using recursion and non-recursion. For more information, please follow other related articles on the PHP Chinese website!