class Node {

    public String value;

    public Node next;

    public Node(String value) {

        this.value = value;

    }

}

public class javaTestLink {

    public static void main(String[] args) {

        Node A = new Node("A");

        Node B = new Node("B");

        Node C = new Node("C");

        Node D = new Node("D");

        Node E = new Node("E");

        Node F = new Node("F");

        A.next = B;

        B.next = C;

        C.next = D;

        D.next = E;

        E.next = F;

        print(A); // 转换之前打印的字符串:A->B->C->D->E->F

        /* 采用递归，从后往前 */

        Node tmpNode = execute2(A);

        print(tmpNode); // 转化后的字符串:F->E->D->C->B->A

        /* 采用非递归，从前往后 */

        // Node tmp = execute2(A);

        // print(tmp); //转化后的字符串:F->E->D->C->B->A

    }

    private static Node execute(Node node) {

        // node看作是前一结点，node.next是当前结点，prev是反转后新链表的头结点

        Node prev = null;

        if (node == null || node.next == null) {

            prev = node; // 若为空链或者当前结点在尾结点，则直接还回

        } else {

            Node tmp = execute(node.next); // 先反转后续节点head.getNext()

            node.next.next = node; // 将当前结点的指针域指向前一结点

            node.next = null; // 前一结点的指针域令为null;

            prev = tmp;

        }

        return prev;

    }

    private static Node execute2(Node node) {

        if (node == null)

            return node;

        Node pre = node; // 上一节点

        Node cur = node.next;// 当前结点

        Node tmp;// 临时节点，用于保存当前结点的指针域（即下一节点）

        while (cur != null) { // 当前结点为null，说明位于尾结点

            tmp = cur.next;

            cur.next = pre; // 反转指针域的指向

            // 指针往下移动

            pre = cur;

            cur = tmp;

        }

        // 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点

        node.next = null;

        return pre;

    }

    private static void print(Node node) {

        while (node != null) {

            System.out.print(node.value);

            node = node.next;

            if (node != null) {

                System.out.print("->");

            } else {

                System.out.println();

            }

        }

    }

}