递归和遍历，逆转单链表

public class MyReverseList {

    public static void main(String[] args){
        Node wn = whileDo(init());
        print(wn);
        Node rn = recursion(init());
        print(rn);

    }

    public static Node init() {
        Node n1 = new Node("1");
        Node n2 = new Node("2");
        Node n3 = new Node("3");
        Node n4 = new Node("4");

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        print(n1);
        return n1;
    }


    public static Node whileDo(Node head) {
        // 1.获取头节点
        Node revNode1 = head;
        // 2.获取第二个节点
        Node revNode2 = head.next;
        // 3.将第一个节点指向null
        revNode1.next = null;
        while (revNode2 != null) {
            // 4.获取第三个节点
            Node revNode3 = revNode2.next;
            // 5.将第二个节点指向第一个节点
            revNode2.next = revNode1;
            // 6.将第二个节点引用传递第一个节点，实现遍历
            revNode1 = revNode2;
            // 7.将第三个节点引用传递第二个节点，实现遍历
            revNode2 = revNode3;
        }
        return revNode1;
    }

    public static Node recursion(Node node) {
        // 递归结束条件，当前节点指向null，即为最后一个节点
        if (node.next == null) {
            return node;
        }
        // 执行递归，返回的是已逆转的node节点
        Node newNode = recursion(node.next);
        // 递归执行后，node.next表示当前node节点指向下一个节点
        // node.next.next则表示当前node节点的下一个节点指向当前节点（重点）
        node.next.next = node;
        // 避免死循环，将node.next置为null
        node.next = null;
        // 直接返回已逆转的节点
        return newNode;
    }

    public static void print(Node head) {
        while (head != null) {
            System.out.print(head.name);
            head = head.next;
        }
        System.out.println();
    }

    static class Node {
        String name;
        Node next;

        public Node(String name) {
            this.name = name;
        }
    }
}