题目
反转一个单链表 leetcode题目链接
示例：
输入：1->2->3->4->5->NULL
输出：5->4->3->2->1->NULL
思路
1. 迭代法
反转一个单链表只需要遍历整个链表，将每个结点的next指针指向前一个节点。
时间复杂度O(n)，空间复杂度O(1)。
c++代码1：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *cur, *prev, *nextn;
prev = head;
if(head == NULL) return NULL;
if(head->next != NULL)
{
cur = head->next;
prev->next = NULL;
}
else
{
return head;
}
while(cur->next != NULL)
{
nextn = cur->next;
cur->next = prev;
prev = cur;
cur = nextn;
}
cur->next = prev;
return cur;
}
};
代码中用到了三个指针，prev指向前一个节点，cur代表当前节点，next代表下一个节点。
其中没有考虑到的情况有：输入的链表是空链表以及只有一个结点的情况。
该代码由于需要判断两次太过冗余，可以将循环的判断条件设置为判断当前节点是否存在，代码会简洁很多。
改进c++代码2
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *cur, *prev, *nextn;
prev = NULL;
cur = head;
while(cur != NULL)
{
nextn = cur->next;
cur->next = prev;
prev = cur;
cur = nextn;
}
return prev;
}
};
简单的修改了一个循环判断条件代码简单了很多。
注意：返回的是prev指针，不是cur指针。
三行Python代码
用python只需要三行就可以完成反转单链表。
使用一行三次赋值的语句只使用到了两个指针cur、prev，避免使用了next指针。
这里使用到了Python的一次性赋值特性，先计算等号右边的值，保存下来后在赋值给等号左边，因此是不需要用到next的指针的。
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur,prev = head, None
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prev
2. 递归法
leetcode官方给出来的第二种解法。
假设当前节点以后的链表已经反转，需要考虑的是当前节点之前的链表如何反转，比如：
链表为：n1->...->ni->nj->...->nm->NULL；
当前节点为nj，nj以后的链接已经成功反转，需要将nj之前的链表反转，针对nj这个节点，需要变成nj->ni，即ni->next->next = ni。（有点绕）
时间复杂度：O(n)
空间复杂度：O(n)，因为递归调用栈
c++递归代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL || head->next == NULL) return head;
ListNode* p = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return p;
}
};
代码分析：
假设链表为1->2->3->4->5->null；
- re(5)，head = 5，因为5->next=null，返回5->null；
- re(4)，head = 4, re(5)返回的是5->null，此时链表为1->2->3->4->5->null，4->next->next = 4执行结果是5->4，链表此时为1->2->3->4<-5，返回5->4->null;
- re(3), head = 3, re(4)返回的是5->4->null，此时链表为1->2->3->4<-5，3->next->next = 3执行结果是5->4->3，链表此时为1->2->3<-4<-5，返回5->4->3->null;
- re(2), head = 2, re(3)返回的是5->4->3->null，此时链表为1->2->3<-4<-5，2->next->next = 2执行结果是5->4->3->2，链表此时为1->2<-3<-4<-5，返回5->4->3->2->null;
- re(1), head = 1, re(2)返回的是5->4->3->2->null，此时链表为1->2<-3->4<-5，1->next->next = 1执行结果是5->4->3->2->1，链表此时为1<-2->3<-4<-5，返回5->4->3->2->1->null;
这时链表已经全部反转完毕。
要注意head->next = NULL这一行代码不能忽略，如果少了这一行代码会出现死循环的情况。
官方解析下面有个评论总结的很到位：我子节点下的所有节点都已经反转好了，现在就剩我和我的子节点没有完成最后的反转了，所以反转一下我和我的子节点。
3. 使用swap()函数
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *p;
for(p=NULL; head; swap(head, p))
swap(p, head->next);
return p;
}
};
使用swap()函数精妙的交换指针。同样三行c++代码
