题目：
给你单链表的头节点 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/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
一、双指针（迭代）
设立两个指针，一个cur指向，初始指向head，一个pre，初始指向null，并设立一个临时变量用于保存cur的下一个结点，循环遍历链表，当cur为null时表示没有后续结点存在，停止循环，循环内做的事：
- 保存cur的下一个结点，存在temp中：temp = cur.next；
- 将当前cur的下一个指针指向pre：cur.next = pre；
- pre向前移动一位：pre = cur；
- cur向前移动一位：cur = temp
最后返回pre。
java代码：
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode() {}
7 * ListNode(int val) { this.val = val; }
8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11 class Solution {
12 public ListNode reverseList(ListNode head) {
13 //申请两个指针,一个指向头结点一个指向空
14 ListNode cur = head;
15 ListNode pre = null;
16 //设置一个临时变量来保存cur的下一个结点
17 ListNode temp = null;
18 //当cur为空表示没有后续结点时停止循环
19 while(cur != null){
20 temp = cur.next;
21 cur.next = pre;
22 //将pre和cur前进一位
23 pre = cur;
24 cur = temp;
25 }
26 return pre;
27 }
28 }
python3代码：
1 # Definition for singly-linked list. 2 # class ListNode: 3 # def __init__(self, val=0, next=None): 4 # self.val = val 5 # self.next = next 6 class Solution: 7 def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: 8 cur = head 9 pre = None 10 11 while cur: 12 temp = cur.next 13 cur.next = pre 14 pre = cur 15 cur = temp 16 17 return pre
二、递归
递归看图解很好理解，但是看代码不是很好理解~ 参考@王尼玛大佬的题解和官方题解下各位大佬的注解
递归的两个条件：
- 终止条件是当前节点或者下一个节点为null(head == null || head.next == null)
- 在函数内部，改变节点的指向，即 head 的下一个节点指向 head ：head.next.next = head
递归函数中每次返回的 cur 其实只是最后一个节点，在递归函数内部，改变的是当前节点的指向。
递归本质是栈，从尾部向前构造，这里出栈要做的事就是建立反向连接并删除正向连接。
举例：1-->2-->3-->4-->5
第一轮：首先一直递归，直到遇到5时，下一个结点为空了，就返回结点5，此时head = 5，head.next = null；
第二轮：head为4，head.next为5，执行head.next.next=head,即5.next = 4
-
把当前节点的子节点的子节点指向当前节点，把5指向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
-
把当前节点的子节点的子节点指向当前节点，把4指向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
-
把当前节点的子节点的子节点指向当前节点，把3指向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
-
把当前节点的子节点的子节点指向当前节点，把2指向1； -
此时链表为1<->2<-3<-4<-5，由于1与2互相指向，所以此处要断开,即1.next=null； -
此时链表为1<-2<-3<-4<-5； -
返回节点5
出栈完成，最终头结点5->4->3->2->1
注意：这里的newhead结点5,就相当于于从1楼爬上五楼拿了一个苹果，然后又从5楼下楼，每下一层楼就展示一下这个苹果。
java代码：
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode() {}
7 * ListNode(int val) { this.val = val; }
8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11 class Solution {
12 public ListNode reverseList(ListNode head) {
13 //设置终止条件
14 if(head == null || head.next == null) return head;
15 //递归传入下一结点，到达尾结点
16 ListNode newHead = reverseList(head.next);
17 head.next.next = head;
18 head.next = null;
19
20 return newHead;
21 }
22 }
python3代码：
1 # Definition for singly-linked list. 2 # class ListNode: 3 # def __init__(self, val=0, next=None): 4 # self.val = val 5 # self.next = next 6 class Solution: 7 def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: 8 if not head or not head.next: 9 return head 10 11 newHead = self.reverseList(head.next) 12 13 head.next.next = head 14 head.next = None 15 16 return newHead
