剑指offer_24_反转链表

class Node {
    public int value;
    public Node next;

    public Node(int data) {
        this.value = data;
    }

    public Node reverseNode(Node head) {
        if(head == null || head.next ==null) {
            return head;
        }
        Node temp = head.next;
        Node newHead = reserve(head.next);
        // 处理头结点
        temp.next = head;
        head.next = null;
        return newHead;
    }

    private Node reserve(Node node) {
        Node pre = null;
        Node next = null;
        while (node != null) {
            // 记录下当前节点的后续节点
            next = node.next;
            // 当前节点的下一个节点指向前一节点
            node.next = pre;
            // 前一节点变成当前节点
            pre = node;
            // 当前节点的下一个节点变成当前节点
            node = next;
        }
        return pre;
    }

    public Node reverse(Node node,Node prev) {
        if (node.next == null) {
            node.next = prev;
            return node;
        } else {
            // 拿到最后的节点，也就是反转后的头结点
            Node rev = reverse(node.next,node);
            node.next = prev;
            return rev;
        }
    }