No test case content is given. No response from the admin. No clear statement is provided. I spent a whole day on the input issue. And I still do not know what is wrong with my original input handler. Save your life, and stay away from this OJ.
Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1505
Question Name: First Common Nodes In Lists
Question Description: Given two integer arrays, find the first node with the same value.
Input: the input might contain multiple test cases. Each test case contains three lines. The first line includes two integers N and M (1 <= N, M <= 1000), saying the number of elements in the two arrays. The second line includes N integers as the content of the first array. And the third line includes M integers as the content of the second array.
Output: for each test case, find the first node with the same value and print out the value, if exist. Otherwise, print “My God”.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | Input: 5 4 1 2 3 6 7 4 5 6 7 3 3 1 5 7 2 4 7 2 3 1 3 4 5 6 Output: 6 7 My God |
The solution is:
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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/07/2014 * Last updated: 09/07/2014 * * Filename: FirstCommonNodesInLists.java * Compilation: javac FirstCommonNodesInLists.java * Execution: java FirstCommonNodesInLists * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * The utility to find the first common node in two single-linked list. * @author Sheng Yu codesays.com */ public class FirstCommonNodesInLists { /** * The definition an operations of single-linked list. * @author Sheng Yu codesays.com */ public static class ListNode { private int value = 0; private ListNode next = null; // Operation on the value field. public ListNode(int val) { value = val; } public ListNode() { value = 0; } public int getVal() { return value; } public void setVal(int val) { value = val; } // Operation on the next field. public void setNext(ListNode n) { next = n; } public ListNode getNext() { return next; } /** * Get the length of the list, starting from this node. * @return the length of this list. */ public int length() { ListNode current = this; int count = 0; while (current != null) { ++count; current = current.getNext(); } return count; } /** * * @param first the head node of the first list. * @param second the head node of the second list. * @return the first common node of the two given lists, if exist. * Otherwise, null. */ public static ListNode getFirstCommonNode(ListNode first, ListNode second){ if (first == null || second == null) return null; ListNode firstCurrent = first; ListNode secondCurrent = second; int firstLen = first.length(); int secondLen = second.length(); // Make the two lists to have the same length. while (firstLen > secondLen){ firstCurrent = firstCurrent.next; --firstLen; } while (firstLen < secondLen){ secondCurrent = secondCurrent.next; --secondLen; } // Find the first common node. // When reaching the end, both pointers are null. while(firstCurrent != null && firstCurrent.value != secondCurrent.value){ firstCurrent = firstCurrent.next; secondCurrent = secondCurrent.next; } return firstCurrent; } } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); ListNode firstHead = new ListNode(); ListNode firstCurrent = null; int firstSize = 0; ListNode secondHead = new ListNode(); ListNode secondCurrent = null; int secondSize = 0; while (st.nextToken() != StreamTokenizer.TT_EOF) { firstSize = (int) st.nval; st.nextToken(); secondSize = (int) st.nval; firstHead.setNext(null); firstCurrent = firstHead; secondHead.setNext(null); secondCurrent = secondHead; while (firstSize-- > 0) { st.nextToken(); firstCurrent.setNext(new ListNode((int) st.nval)); firstCurrent = firstCurrent.getNext(); } while (secondSize-- > 0) { st.nextToken(); secondCurrent.setNext(new ListNode((int) st.nval)); secondCurrent = secondCurrent.getNext(); } ListNode common = ListNode.getFirstCommonNode(firstHead.getNext(), secondHead.getNext()); if (common == null) System.out.println("My God"); else System.out.println(common.getVal()); } } } |