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

韦小宝
發布: 2023-03-21 11:44:02
原創
1534 人瀏覽過

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

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!