单链表反转的递归与非递归实现

忘是亡心i 2022-06-09 00:11 198阅读 0赞

此题来源于leetcode 206.单链表反转  
Difficulty:Easy  
在题目中给出了可使用递归与迭代两种算法的提示。  
因为对递归理解不深刻，首先采用迭代编写算法，在题目中的head结点认为是含有数据的第一个结点  
题目思路：从头结点出发，向后遍历，按照顺序一个个逐渐实现结点之间链的反转。  
首先尝试使用2个指针完成操作，失败  
class Solution \{  
public:  
ListNode\* reverseList(ListNode\* head) \{  
ListNode\* pre = NULL;  
while(head -> next)  
\{  
pre = head;  
head = head -> next;  
head -> next = pre;  
\}  
return head;  
\};  
理由如下：在反转过程中，head ->next 已经反向，无法继续向后遍历，因此增加一个指针采用3个指针完成操作  
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  
\};  
  
递归不会，参考Discuss后，理解。  
思路如下：通过递归使得头结点不断向后遍历，直到终止条件：达到尾结点 后停止。  
代码如下：  
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;  
\};  
到达递归终止条件时呈现的状态如下：  
  
![Center][]  
  
  
返回上一层递归后状态如下：  
  
![Center 1][]  
经过注释1、2的两行代码后，状态如下  
  
![Center 2][]  
可见head结点的位置与递归层数有关，而temp作为反转后的头结点，位置始终不动，从而达到反转效果。  
递归代码虽能看懂，然而我现在还并不会设计，还是个菜鸡。

[Center]: /images/20220609/0fbaab8b46c64f16954146437acd86c5.png
[Center 1]: /images/20220609/e08ee7b6b5ac442d867838c4438fdf59.png
[Center 2]: /images/20220609/c3447ae92923471a8316619ae3fe3184.png