反转链表-力扣

该题使用虚拟头节点来做在思考的时候稍微有点复杂，但与从头节点开始，利用一个cur节点来反转流程是一样的，只需将dummyhead->next 当作是 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) {ListNode * dummyhead = new ListNode(0);ListNode * pre = NULL;ListNode * tmp = NULL;dummyhead->next = head;while(dummyhead->next != NULL){tmp = dummyhead->next->next;dummyhead->next->next = pre;pre = dummyhead->next;dummyhead->next = tmp;}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) {ListNode * pre = NULL;ListNode * tmp = NULL;ListNode * cur = head;while(cur != NULL){tmp = cur->next;cur->next = pre;pre = cur;cur = tmp;}return pre;}
};

使用迭代的写法，代码如下：

class Solution {
public:ListNode* reverse(ListNode* pre, ListNode* cur){if(cur == NULL){return pre;}ListNode* tmp = cur->next;cur->next = pre;return reverse(cur,tmp);}ListNode* reverseList(ListNode* head) {return reverse(NULL,head);}
};