翻转单向链表

QUESTION:

给定一个单向链表，将它进行翻转，并返回表头。
例如：1->2->3->4，返回：4->3->2->1

EXPLANATION:

首先这道题目可以采用两种方式，一种是递归的方式，一种是循环的方式。
循环方式的逻辑：
1.首先拿到第一个也就是1
2.创建一个新的node来保存这个值，并且标记为head
3.当1后面还有值的时候，也就是需要继续往后循环，那么创建第二个值来保存2
4.同时将2的next设置为1，这样就完成了2->1的链接，同时将2保存在head上 5.循环3-4两步，知道链表遍历结束

递归方式的逻辑：以1->2->3->4为例
1.首先需要找到最后一个节点4
2.将最后一个节点的next设置为上一个节点4->3,1->2->3->4 3.同时断开上一个节点的next4->3,1->2->3
4.关键点是这时候倒数第二个其实有两个指针
5.依次递归就能将链表进行翻转

SOLUTION:

    public static Node revertNode(Node node){
        Node head = new Node(node.val);
        while (node.next!=null){
            Node next = node.next;
            Node n = new Node(next.val);
            n.next = head;
            head = n;
            node = node.next;
        }
        return head;
    };

    public static Node revertNode(Node node){
        if(node==null || node.next==null) return node;
        Node newNode = revertNode(node.next);
        node.next.next = node;
        node.next = null;
        return newNode;
    }
--> return <--