链表翻转也是个经典问题，题目：单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

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

示例 3：

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

ListNode表示链表，leetcode题目中提供的

public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

翻转链表分析

下面这张图能更好的理解翻转链表，核心是箭头的方向发生改变，设置3个变量：pre是前一个节点，cur是当前节点，next是下一个节点。将当前节点的next指向pre前一个节点，同时pre为下一轮循环做准备

方法1：非递归方式实现

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            // 完成当前节点的反转
            cur.next = pre;
            // 为下一轮循环做准备
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

方法二：递归方式实现

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 理解方式：递归调用类似于栈，这样除了head之外，其他链表指向都发送了翻转，
        // 例如1->2->3->4->5递归调用后变成2<-3<-4<-5
        ListNode rev = reverseList(head.next);
        // 准确来说是这样的 1->2 null<-2<-3<-4<-5，因此下面俩句来解决head指向问题
        head.next.next = head;
        head.next = null;
        return rev;
    }
}