反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

输入：head = [1,2,3,4,5]

输出：[5,4,3,2,1]

tips:

• 链表中节点数的数目范围 [0,5000]
• -5000 <= Node.val <= 5000

方法1——双指针迭代

 1 class Solution {
 2     public ListNode reverseList(ListNode head) {
 3 
 4         //双指针
 5         //创建结点，先结点start指向head，后结点end指向null
 6         ListNode start = head, end = null;
 7         //循环迭代
 8         while(start != null){
 9             //临时结点保存下结点值
10             ListNode tmp = start.next;
11             //当前结点指向end开始反转
12             start.next = end;
13             //start和end都向前移动
14             end = start;
15             start = tmp;
16         }
17         return end;
18     }
19 }

方法2——递归

 1 class Solution {
 2     public ListNode reverseList(ListNode head) {
 3 
 4         //递归条件：当前结点为空或者下结点为空
 5         if(head == null || head.next == null){
 6             return head;
 7         }
 8         //申请结点end指向链表最后一个结点
 9         ListNode end = reverseList(head.next);
10         //重新指向
11         head.next.next = head;
12         //防止链表循环，需吧head.next设置为null
13         head.next = null;
14         //每层递归函数都返回end，也就是最后一个结点
15         return end;
16 
17     }
18 }