第二講：反轉連結清單

題目：AcWing 35. 反轉連結清單

定義一個函數，輸入一個連結清單的頭結點，反轉該連結清單并輸出反轉後連結清單的頭結點。

思考題：

請同時實作疊代版本和遞歸版本。

資料範圍

連結清單長度 [0,30]。

樣例

輸入:1->2->3->4->5->NULL

輸出:5->4->3->2->1->NULL

方法一： 疊代版本

1.使用 指針pre和next分别儲存head的前節點和後節點

2.将head目前節點的next指向pre節點，将head指向next後節點

3.循環傳回pre節點即可（因為最後有空節點）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next)return head;
        ListNode *pre=NULL;
        while(head)
        {
            ListNode *next=head->next;
            head->next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
};
           

方法二： 遞歸版本

因為先會遞歸到最後節點，然後慢慢傳回

假設在3節點時，會傳回5->4->NULL

1.目前節點的next節點是指向末尾節點

2.隻需要使用目前節點找到末尾節點，然後再末尾節點的next指向目前節點即可

3.将目前節點next置為NULL

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