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

示例 1：

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

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

解题思路

解法一：递归法

1. 递归的终止：遍历完了 【head.next == null return head】
2. 返回什么： 反转好的链表 【返回原链表的头（示例1的节点⑤）】
3. 当前层级要做什么：

 head  ->  next
            ↑
        将当前的head反转【head.next.next = head ,  head.next = null】

解法二：迭代法

1. 要做什么？ head.next= prev
2. 会导致什么？ 原来的 next 找不到了
3. 怎么解决？ 提前保存 next 【 ListNode next = head.next 】

Java 实现

递归法

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        // 这个是事实的尾节点，从始至终没有动过它
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null; //  1 -> 2 变为 2 -> 1 时，没有下一次递归了，因此需要先置空
        return last;
    }

迭代法

    private ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
    }