LeetCode 206 Reverse Linked List（反轉鏈表）（四步將遞歸改寫成迭代）（*）

LeetCode 206 Reverse Linked List（反轉鏈表）（四步將遞歸改寫成迭代）（*）

翻譯

反轉一個單鏈表。

原文

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(nextNode, head);
}

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

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);
    }
}