Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1511
Question Name: Print List from End
Question Description: giving a single-linked list, print the values of its nodes from end to beginning.
Input: multiple lines. Each line is an integer. -1 means reaching the end of list. And -1 is not a part of the list.
Output: the values in reversed order.
1 2 3 4 5 6 7 8 9 10 11 12 13 | Input: 1 2 3 4 5 -1 Output: 5 4 3 2 1 |
The solution is easy with stack.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | /** * Filename : PrintListFromEnd.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-07-31 * JDK used : 1.7 * Changelog : None */ import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Stack; import java.io.IOException; /** * Definition for singly-linked list and its operation. */ class ListNode { public Object val; public ListNode next; /** * The constructor of ListNode * @param x: an object to be the value of this ListNode. */ public ListNode(Object x) { val = x; next = null; } /** * Print a list from the end to the beginning. * @param head: the head node of the to-print list. */ static public void printListFromEnd(ListNode head) { Stack<Object> values = new Stack<Object>(); // Travel the list from beginning to end, and push the value of // all nodes into the stack. ListNode current = head; while (current != null) { values.push(current.val); current = current.next; } // Pop the stack and print the popped item, until the stack is empty. // Because the FILO of stack, the tailing nodes are printed before // the head part. while (!values.empty()) { System.out.println(values.pop()); } return; } } public class PrintListFromEnd { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int nextNum = -1; ListNode pseudoHead = new ListNode(-1); ListNode current = pseudoHead; // Construct the list from stdin. while (st.nextToken() == StreamTokenizer.TT_NUMBER) { nextNum = (int)st.nval; if (nextNum == -1) break; current.next = new ListNode(nextNum); current = current.next; } // Print the list in reversed order. ListNode.printListFromEnd(pseudoHead.next); } } |