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) {ListNode* pre = nullptr;ListNode* cur = head;while(cur){ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}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) {return reverse(head,nullptr);}ListNode* reverse(ListNode* cur,ListNode* pre){if(cur == nullptr)return pre;ListNode* temp = cur->next;cur->next = pre;return reverse(temp,cur);}
};

 另一种写法

/*** 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 || !head->next){return head;}ListNode* newHead = reverseList(head->next);head->next->next = head;head->next = nullptr;return newHead;}
};