原題鏈接：Leetcode 206. 反轉鏈表

解法一：迭代

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

解法二：遞歸

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode *head) {if(head==nullptr || head->next==nullptr) return head;// 「遞」到鏈表末尾，拿到新鏈表的頭節點(舊鏈表的尾節點)ListNode* newhead = reverseList(head->next);// 讓下一個節點指向自己head->next->next = head;// 斷開原來的指針head->next = nullptr;return newhead;}
};
// 鏈表：1 -> 2 -> 3 -> 4 -> 5
// 遞歸調用順序：
// reverseList(1)
//     reverseList(2)
//         reverseList(3)
//             reverseList(4)
//                 reverseList(5)
// 5->next==nullptr,返回 5
// newhead=5,head=4, 4->next=5, 5->next = 4(反轉)，4->next=nullptr
// newhead=5,head=3, 3->next=4, 4->next = 3(反轉)，3->next=nullptr
// newhead=5,head=2, 2->next=3, 3->next = 2(反轉)，2->next=nullptr
// newhead=5,head=1, 1->next=2, 2->next = 1(反轉)，1->next=nullptr
// return  newhead=5