class ListReverse {

    protected static CharLinkNode reverseList (CharLinkNode head) {

	if ((head == null) || (head._next == null)) {

	    // Handles an empty list or a one-element list.
	    return head;

	} else {

	    // In the middle of the list.
	    CharLinkNode reversedHead = reverseList(head._next);
	    head._next._next = head;
	    head._next = null;
	    return reversedHead;
	    
	}

    }

    protected static CharLinkNode constructList (String s) {

	CharLinkNode head = null;
	for (int index = s.length() - 1; index >= 0; index--) {

	    head = new CharLinkNode(s.charAt(index), head);

	}

	return head;

    }

    protected static void emitList (CharLinkNode head) {

	if (head == null) {

	    System.out.println();

	} else {

	    System.out.print(head._value);
	    emitList(head._next);

	}

    }

    public static void main (String[] args) {

	System.out.print("Enter a string: ");
	String s = User.readLine();

	CharLinkNode originalHead = constructList(s);
	emitList(originalHead);

	CharLinkNode reversedHead = reverseList(originalHead);
	emitList(reversedHead);

    }

}