LeetCode 206 Reverse Linked List（反轉連結清單）（Linked List）（四步将遞歸改寫成疊代）（*）

版權聲明：轉載請聯系本人，感謝配合！本站位址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50514593

翻譯

反轉一個單連結清單。           

原文

Reverse a singly linked list.           

分析

我在草紙上以1,2,3,4為例，将這個連結清單的轉換過程先用描繪了出來（當然了，自己畫的肯定不如部落格上面精緻）：

有了這個圖（每次把部落格發出去後就會發現圖怎麼變得這麼小了哎！隻能麻煩大家放大看或者另存為了，這圖命名是1400X600的），那麼代碼也就自然而然的出來了：

ListNode* reverseList(ListNode* head) {
    ListNode* newHead = NULL;
    while (head) {
        ListNode* nextNode = head->next;
        head->next = newHead;
        newHead = head;
        head = nextNode;
    }
    return newHead;
}           

上面用的是遞歸，下面就接着來看看如何把遞歸改寫成疊代。他們的共同點無非就是都有值在不停的進行變換更疊，大家回顧一下上圖會發現就是這裡的head和newHead。是以接下來就把這兩個值作為疊代循環的參數。

遞歸轉疊代

第一步：先寫出疊代的模闆，以及設定好的參數。

ListNode* reverseListIter(ListNode* head, ListNode* newHead) {

}

ListNode* reverseList(ListNode* head) {

}           

第二步：為第一次疊代設定初始值。如果已經遺忘了的話，請看上面的遞歸代碼，newHead一開始是等于NULL的，是以增加代碼如下。

ListNode* reverseListIter(ListNode* head, ListNode* newHead) {

}

ListNode* reverseList(ListNode* head) {
    return reverseListIter(head, NULL);
}           

第三步：上面的一二步可以說是通用的，但從第三步開始就要根據特定的遞歸過程來改寫了。首先是判斷疊代停止的條件，上面遞歸過程中停止的條件是head為空，這裡照搬。

ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
    if (head == NULL) return newHead;
}           

緊接着遞歸中有兩個初始的指派，這裡也一并複制過來：

ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
    if (head == NULL) return newHead;
    ListNode* nextNode = head->next;
    head->next = newHead;
    return reverseListIter(head, newHead);
}           

第四步：更新疊代的參數。可以看到遞歸代碼更新方式如下：

newHead = head;
head = nextNode;           

你當然也可以直接這樣寫到疊代中，但既然用了參數，何不把這過程在代碼形式上簡化一下呢？

ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
    if (head == NULL) return newHead;
    ListNode* nextNode = head->next;
    head->next = newHead;
    return reverseListIter(nextNode, head);
}           

那麼這樣就完成了整個疊代的過程了，棒！

有兩個地方需要注意一下：

1，一定要記得return。

2，第一行判斷後，傳回的是newHead。
這是因為當newHead為空時，傳回newHead也是傳回空；
當newHead不為空時，其則要作為結果傳回給reverseList函數。           

其實把改寫的過程拆解來看是非常容易了解的，希望我的部落格能夠幫到大家……

代碼

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
        if (head == NULL) return newHead;
        ListNode* nextNode = head->next;
        head->next = newHead;
        return reverseListIter(nextNode, head);
    }

    ListNode* reverseList(ListNode* head) {
        return reverseListIter(head, NULL);
    }
};