力扣206. 反转链表
一、题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]示例 2：
输入：head = [1,2]输出：[2,1]示例 3：
输入：head = []输出：[]
提示：
链表中节点的数目范围是 [0, 5000]-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-linked-list著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思路分析：
这道题考察了什么思想？你的思路是什么？
- 思路有点难理解，不过画个图一步一步推理就容易明白了。
我们得先保留下一个节点的地址，然后将第一个节点指向空节点，然后移动这些坐标，将第二个节点指向第一个节点，以此类推。。。
做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？
- 不是一次通过的，我们得考虑链表为空的情况，刚开始我没有考虑就取next= head->next，当然我们直接在前面用个if判断语句就行了。
有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？
- 还有一种递归解法，确实有点难理解。
下面是力扣作者NoColor96的解析，我认为解释得十分清楚，可以供各位参考。
/**
* 以链表1->2->3->4->5举例
* @param head
* @return
*/
publicListNodereverseList(ListNodehead) {
if (head==null||head.next==null) {
/*
直到当前节点的下一个节点为空时返回当前节点
由于5没有下一个节点了，所以此处返回节点5
*/
returnhead;
}
//递归传入下一个节点，目的是为了到达最后一个节点
ListNodenewHead=reverseList(head.next);
/*
第一轮出栈，head为5，head.next为空，返回5
第二轮出栈，head为4，head.next为5，执行head.next.next=head也就是5.next=4，
把当前节点的子节点的子节点指向当前节点
此时链表为1->2->3->4<->5，由于4与5互相指向，所以此处要断开4.next=null
此时链表为1->2->3->4<-5
返回节点5
第三轮出栈，head为3，head.next为4，执行head.next.next=head也就是4.next=3，
此时链表为1->2->3<->4<-5，由于3与4互相指向，所以此处要断开3.next=null
此时链表为1->2->3<-4<-5
返回节点5
第四轮出栈，head为2，head.next为3，执行head.next.next=head也就是3.next=2，
此时链表为1->2<->3<-4<-5，由于2与3互相指向，所以此处要断开2.next=null
此时链表为1->2<-3<-4<-5
返回节点5
第五轮出栈，head为1，head.next为2，执行head.next.next=head也就是2.next=1，
此时链表为1<->2<-3<-4<-5，由于1与2互相指向，所以此处要断开1.next=null
此时链表为1<-2<-3<-4<-5
返回节点5
出栈完成，最终头节点5->4->3->2->1
*/
head.next.next=head;
head.next=null;
returnnewHead;
}
三、AC 代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
structListNode*reverseList(structListNode*head){
if(head==NULL) returnhead;
structListNode*next=NULL;
structListNode*n=NULL;
while(head){
next=head->next;
head->next=n;
n=head;
head=next;
}
returnn;
}
四、总结：
递归方法要好好理解。
