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