反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnhm6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法1.逆置优先想到栈

1.遍历链表，元素入栈
2.设置一个始终指向队尾的变量，依次将元素退栈，链尾元素连接新出栈元素，链尾后移
3.最后一个元素next置空
4.返回第一个出栈的元素

    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode p = head;
        while(p != null){
            stack.push(p);
            p = p.next;
        }
        p = stack.pop();
        head = p;
        while(!stack.empty()){
            p.next = stack.pop();
            p = p.next;
        }
        p.next = null;
        return head;
    }

方法2.直接逆置

1.设置一个新链头，始终指向新链头元素，head始终指向旧链头
2.按照逆置关系，旧链头应该指向新链头，但是直接旧.next = 新 会丢失当前旧.next,所以设置一个临时变量暂存旧.next，然后在进行连接
3.连接后，保持两个链头元素的位置
4.返回新链头

public ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }

方法3.递归

逆置可以把大问题分解成解决过程一样的子问题然后在反过来解决大问题吗？
考虑传入的元素是头结点，方法目的是把头结点对应的链表逆置返回头节点，那么如果传入头结点的next，将他对应的链表逆置返回其头结点，解决的问题是一样的->当前问题和子问题解决方法一致。
这时只需要把当前节点连接到新链表的尾部，也就是原头结点的next.next就解决了当前问题->解决子问题后可以解决当前问题。
所以，可以使用递归。
1.递归出口为当前元素的next为空(既然为空那就算不上一个子问题)
2.递归head.next返回新链表
3.将head连接到新链链尾 head.next.next = head
4.head成为新链尾，故next置空
5.返回本轮问题的解->逆置后的链头

public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode headNext = head.next;
        ListNode newHead = reverseList(headNext);
        headNext.next = head;    //(head.next.next = head)
        head.next = null;
        return newHead;
    }