反转单向链表

前置：

static class MyNode {
        int val;
        MyNode preNode;
        MyNode nextNode;

        public MyNode(int val, MyNode preNode, MyNode nextNode) {
            this.val = val;
            this.preNode = preNode;
            this.nextNode = nextNode;
        }

        ;
    }

    public static void main(String[] args) {
        MyNode head = new MyNode(1, null, null);
        MyNode head1 = new MyNode(2, null, null);
        MyNode head2 = new MyNode(3, null, null);
        MyNode head3 = new MyNode(4, null, null);
        head.nextNode = head1;
        head1.preNode = head;
        head1.nextNode = head2;
        head2.preNode = head1;
        head2.nextNode = head3;
        head3.preNode = head2;

        MyNode heads = reverseNode(head);
        while (heads != null) {
            System.out.println(heads.val);
            heads = heads.nextNode;
        }

    }

普通解法： 

//其核心原理便是，遍历链表，逐个反转，所有的程序都是为这2目标服务
    private static MyNode reverseNode(MyNode head) {
        //关键步骤，1循环遍历，2逐个反转next
        MyNode temp = head;
        MyNode pre = null;

        while (head != null) {
            //为了循环遍历
            temp = temp.nextNode;
            //反转
            head.nextNode = pre;
            //准备下一次反转
            pre = head;
            //准备下一次遍历
            head = temp;
        }
        return pre;
    }

递归解法：

//使用递归反转链表
    private static MyNode reverseNodeByRecursion(MyNode head) {
        return recursionNode(null, head);
    }

    private static MyNode recursionNode(MyNode pre, MyNode head) {
        if (head == null) return pre;
        MyNode temp = head.nextNode;
        head.nextNode = pre;
        pre = head;
        return recursionNode(pre, temp);
    }