使用遞歸和非遞歸實現單鏈反轉詳解

這篇文章講述了使用遞歸以及非遞歸如何實現單鏈反轉，可能有很多同學並不太了解單鏈反轉是什麼，那麼就讓我們廢話少說，直接看本篇文章吧！
在題目中給出了可使用遞歸與迭代兩種演算法的提示。
因為對遞歸理解不深刻，首先採用迭代編寫演算法，在題目中的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;
};

到達遞迴終止條件時呈現的狀態如下：




返回上一層遞迴後狀態如下：


##經過註解1、2的兩行程式碼後，狀態如下


#可見head結點的位置與遞歸層數有關，而temp則作為反轉後的頭結點，位置始終不動，因此達到反轉效果。 遞迴程式碼雖能看懂，然而我現在還並不會設計，還是個菜雞。

#相關文章：

PHP實現單鏈表翻轉操作範例

#

以上是使用遞歸和非遞歸實現單鏈反轉詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！