Leetcode206.反转链表(HOT100)

链接：

我的代码：

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* p = head;ListNode*res = new ListNode(-1);while(p){ListNode*k = res->next;res->next = p;p = p->next;res->next->next = k;}return res->next;}
};

我用的是迭代实现。 

更好的代码： 

class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head)return nullptr;ListNode* a = head,*b = head->next;while(b){ListNode*c = b->next;b->next = a;a = b;b = c;}head->next = nullptr;return a;}
};

第一步：

第二步：
 

最后一步：
 

此时，别忘了，head仍然指向原来的头结点，这个头结点现在是尾节点了，所以把它的next置空。

 更好的代码（递归实现）：

class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head||!head->next)return head;auto tail = reverseList(head->next);head->next->next = head;head->next = nullptr;return tail;}
};

 图示：

 

 

上图是head->next->next = head;

完毕。