定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

1.双指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode pre = null, lat = head;
        // ListNode dummy = lat;
        while(lat != null){
            ListNode tmp = lat.next;
            // ListNode tmp1 = lat;
            // lat.next = pre;
            // pre = tmp1;
            // lat = tmp;
            lat.next = pre;
            pre = lat;
            lat = tmp;
        }
        return pre;
    }
}

2.递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode node = reverseList(head.next);
        // if(node == null){
        //     return head;
        // }else{
            // node.next = head;//???node一直是5开头，node每次更换下一个，所以最后5，1
            head.next.next = head;
            head.next = null;
        // }
        return node;
    }
}

3.栈

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        Stack<Integer> stack = new Stack<Integer>();
        while(head!=null){
            stack.push(head.val);
            head = head.next;
        }
        if(stack.isEmpty()){
            return null;
        }
        ListNode node = new ListNode(stack.pop());
        ListNode pre = node;//记录一下头
        while(!stack.isEmpty()){
            ListNode dummy = new ListNode(stack.pop());
            node.next = dummy;
            node = node.next;
        }
        return pre;


    }
}