Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1518
Question Name: Reverse List
Question Description: Give an single-linked list, reverse it in place.
Input: the input might contain multiple test cases. Inside each test case, the first line is one interger N (0 <= N <= 1000), saying the size of the list. The second line includes N integers, as the value of each node in the list.
Output: “NULL” if N is 0. Otherwise, reverse the list, and print out the value of each node in the reversed list from beginning to end.
1 2 3 4 5 6 | Input: 5 1 2 3 4 5 Output: 5 4 3 2 1 NULL |
Classic problem.
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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | /** * Filename : ReverseList.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-08-07 * JDK used : 1.7 * Change log: None */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class ReverseList { /** * Definition for singly-linked list and its operation. */ static private 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; } /** * @return Returns a string representing the data in this list. */ public String toString(){ String result = new String(this.val.toString()); if (this.next != null) result = result + " " + this.next.toString(); return result; } } /** * Reverse the list in place. * @param head : the head of to-reverse list. * @return ListNode: the head of reversed list. */ private ListNode reverseList(ListNode head) { // This is the last node. if (head.next == null) return head; // Process the remaining node firstly. ListNode newHead = reverseList(head.next); // Reverse current node and its next node. head.next.next = head; head.next = null; return newHead; } /** * Stub for test. * @param args * @throws IOException */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int size; ReverseList reverser = new ReverseList(); ListNode head = null, current = null; while (st.nextToken() != StreamTokenizer.TT_EOF) { // Start a new test case. size = (int) st.nval; if (size == 0) { System.out.println("NULL"); continue; } // Get the test array. head = current = null; while (size > 0) { st.nextToken(); if (head == null) { current = head = new ListNode((int) st.nval); } else { current.next = new ListNode((int) st.nval); current = current.next; } --size; } // Reverse the list. head = reverser.reverseList(head); System.out.println(head); } } } |