leadcode的Hot100系列--206. 反轉鏈表

這裡使用兩種方式，
一個是直接從頭往後遍歷 -------> 迭代
一個是從最後一個往前遍歷 -----> 遞歸

迭代

定義三個變數：pPre pNext pNow
pPre表示當前節點的前一個地址，pNext表示當前節點的下一個地址，pNow表示當前節點的地址。

反轉的核心：就是把 pNow的next指針，指向 pPre

因為反轉之後，pNow的next原來的值會丟，所以在反轉之前，要用pNext把原來的值保存一下。
反轉之後，要處理下一個節點，而本節點就是下一個節點的前一個節點，所以用pPre把當前節點地址保存一下。

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *pstPre = NULL;
    struct ListNode *pstNow = head;
    struct ListNode *pstNext = NULL;
    
    while (NULL != pstNow)
    {
        pstNext = pstNow->next;  // 先保存一下當前節點的next指針
        pstNow->next = pstPre;    // 做反轉
        pstPre = pstNow;              // 更新pstPre指針
        pstNow = pstNext;            // 繼續做下一個節點的反轉
    }
    return pstPre;
}

遞歸

遞歸的話，不太好理解，先上代碼，看著代碼來理解：

struct ListNode* reverseList(struct ListNode* head){
    struct ListHode *pstNewHead = NULL;
    if (head == NULL || head->next == NULL)   // 如果鏈表為空，或者是最末端節點，則直接返回當前節點地址
    {
        return head;
    }
    else
    {
        pstNewHead = reverseList(head->next);  // 返回新鏈表頭節點
        head->next->next = head;  // 這裡完成反轉
        head->next = NULL;
        
        return pstNewHead;
    }
}

遞歸寫法的關鍵是：head->next->next = head 這句代碼中，
head 是誰，head->next 是誰，head->next->next 又是誰！

可以從後往前理解，假設有三個節點，為 1 -> 2 -> 3，

最後一次：當head為節點2時，入參為傳入節點3，節點3的next為NULL，返回節點3的地址。

此時：head指向節點2，pstNewHead指向節點3，
-----> 得到：head->next 指向節點3，head->next->next 就相當於節點3的next，
所以：執行完 "head->next->next = head"之後，就相當於把節點3的next指向了節點2，完成一個反轉。
而節點2的next指針已經沒用了（原本節點2的next指向了節點3），直接指向NULL。
上面部分實現了節點3與節點2的反轉，並此時pstNewHead指向了節點3。

再繼續。
上面返回pstNewHead為節點3的地址，此時入參的head為1（因為之前head為節點2，返回調用者的時候，是head->next為節點2，所以這裡調用者為節點1），
所以，head->next為2，head->next->next 就相當於是節點2的next，所以執行完 "head->next->next = head"之後，就相當於把節點2的next指向了節點1。
而節點1原來的next沒用了（原本節點1的next指向了節點2），直接指向NULL，這裡就相當於是鏈表尾部。
然後返回pstNewHead。
其實這裡pstNewHead只賦值過一次，之後從未改變，一直指向了最一開始的節點3。