Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1519
Question Name: Merge Sorted List
Question Description: Give two sorted single-linked lists, merge them.
Input: the input might contain multiple test cases. Inside each test case, the first line includes two interger N and M (0 <= N, M <= 1000), saying the size of the first and second lists respectively. The second line includes N integers, as the value of each node in the first list. The thid line includes M integers for the second list.
Output: “NULL” if merged list is empty. Otherwise, print out the merged list..
1 2 3 4 5 6 7 8 | Input: 5 2 1 3 5 7 9 2 4 0 0 Output: 1 2 3 4 5 7 9 NULL |
The output matters a lot in the OJ system. A recursive toString() will lead to Time Limit Exceed.
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 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/08/2014 * Last updated: 08/08/2014 * * Filename: MergeSortedList.java * Compilation: javac MergeSortedList.java * Execution: java MergeSortedList * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * This class include a definition of ListNode, and the function to * merge two sorted list. * @author Sheng Yu codesays.com */ public class MergeSortedList { /** * Definition for singly-linked list and its operation. * @param <T> the type of the value in the node. */ private static class ListNode<T> { /** The variable to store the value of the node. */ private T val; /** The link to the next ListNode. May be null. */ private ListNode<T> next; /** * The constructor of ListNode. * @param x the value of this node. */ public ListNode(final T x) { val = x; next = null; } /** @return the value of current node. */ public T getVal() { return val; } /** @param newValue set the value of this node to be newValue. */ public void setVal(final T newValue) { val = newValue; } /** @return the next node of current node. */ public ListNode<T> getNext() { return next; } /** @param newNode set the next node to be newNode. */ public void setNext(final ListNode newNode) { next = newNode; } /** * @return Returns a string representing the data in this list. */ public String toString() { StringBuilder sb = new StringBuilder(); ListNode<T> current = this; sb.append(current.getVal()); current = current.next; while (current != null) { sb.append(" "); sb.append(current.getVal()); current = current.next; } return sb.toString(); } } /** * The two given lists are already sorted. This function is going to * merge them into one list. * @param first the head node of the first list. * @param second the head node of the second list. * @return the head node of merged list. */ public final ListNode<Integer> mergeSortedList(ListNode<Integer> first, ListNode<Integer> second) { ListNode<Integer> pseudoHead = new ListNode<Integer>(null); ListNode<Integer> current = pseudoHead; while (first != null && second != null) { if (first.getVal() <= second.getVal()) { // first node has smaller or equal value. Append it. current.next = first; first = first.getNext(); } else { // Second node has smaller value. Append it. current.next = second; second = second.getNext(); } current = current.next; } if (first != null) { // First list holds remaining nodes. current.next = first; } if (second != null) { // Second list holds remaining nodes. current.next = second; } return pseudoHead.next; } /** * Stub for test. * @param args command line arguments * @throws IOException if getting input meets error. */ public static void main(final String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); StringBuilder sb = new StringBuilder(); int firstSize = 0, secondSize = 0; ListNode<Integer> first = null, second = null, current = null, result = null; MergeSortedList merger = new MergeSortedList(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Get the size of the two lists. firstSize = (int) st.nval; st.nextToken(); secondSize = (int) st.nval; // Get the first list. first = null; if (firstSize != 0) { st.nextToken(); first = new ListNode<Integer>((int) st.nval); current = first; while (--firstSize > 0) { st.nextToken(); current.next = new ListNode<Integer>((int) st.nval); current = current.next; } } // Get the second list. second = null; if (secondSize != 0) { st.nextToken(); second = new ListNode<Integer>((int) st.nval); current = second; while (--secondSize > 0) { st.nextToken(); current.next = new ListNode<Integer>((int) st.nval); current = current.next; } } // Merge the lists, and print the result. result = merger.mergeSortedList(first, second); if (result == null) { sb.append("NULLn"); } else { sb.append(result.toString()); sb.append("n"); } } System.out.print(sb); } } |