题目链接：https://leetcode.com/problems/reverse-linked-list/
方法一：迭代反转
https://blog.csdn.net/qq_17550379/article/details/80647926讲的很清楚
/**
* 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) {
ListNode* pre = NULL;
ListNode* cur = head;
ListNode* lat;
while(cur){
lat = cur -> next;
cur -> next = pre;
pre = cur;
cur = lat;
}
return pre;
}
};
方法二：递归反转
解决递归问题从最简单的case入手。
（1）例如，对于链表1->2->3->4->5，
reverseList(head)返回的是5->4->3->2->1；
reverseList(head->next)返回的是5->4->3->2;（因为head->next所指代的链表是2->3->4->5->NULL）
以此类推。
（2）对于reverseList(3)这个情况，此时head为3，head->next为4，此时链表情况如下：
1->2->3->4<-5
head->next->next=head这一操作后，链表变为：
然后，head->next=NULL，即
1->2->3<-4<-5
/**
* 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 == NULL || head -> next == NULL)
return head;
ListNode *ans = reverseList(head -> next);
head -> next -> next = head;
head -> next = NULL;
return ans;
}
};
此外，提供一个错误写法：
/**
* 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 == NULL || head -> next == NULL)
return head;
ListNode *ans = reverseList(head -> next);
ans -> next = new ListNode(head -> val);
return ans;
}
};
这种写法的错误之处在于：
以reverseList(3)为例，虽然ListNode *ans = reverseList(head -> next);返回的是5->4这个链表，不过ans指的是这个链表的第一个结点5，然后ans->next=new ListNode(head->val)后，其实在当前这一层递归中最终return的是5->3这个链表，并不是返回想象中的5->4->3这个链表。
参考：https://blog.csdn.net/qq_17550379/article/details/80647926