Description

You will be given two sorted linked lists A and B with no duplicate numbers in each list (but a number in list A might appear in list B).

Both lists A and B are sorted in increasing order.

Each node stores an integer ranging from 0 to 999,999,999.

Your task is to merge lists A and B into a new linked list C, where the numbers in list C are still sorted in increasing order, i.e., the smallest number is the first node in the list.

We will use a pre-defined function PrintChain to evaluate your answer, which takes head of list C as input and scans through the whole list to print every element. 

 

The definitions of list node and PrintChain are given in the header file.

Your task is to implement the Merge function, which takes the heads of lists A and B as input, and returns the head of list C.

You must include "function.h". Failing to do so will result in a disqualification (i.e., get 0 points in this quiz).

Don't sumbit code with a main function. Just the implementation of the Merge function.

In order to make PrintChain work, please select C++11 or later version in Online Judge.

 

Note that <algorithm> is not allowed. That is, you cannot use any function in <algorithm>, e.g., sort, stable_sort, etc. Including <bits/stdc++.h> header and using the abovementioned functions are also not allowed. Additionally, qsort in <cstdlib>, <stdlib.h> is also not allowed.

 

Hints:

1. Remember to add: #include "function.h".
2. You can allocate a new node in the following way:
   Node *newNode = new Node( some_integer , NULL );
3. For each test case, there might be multiple sets of lists A and B for you to merge into C. For your convenience, we have implemented the function for reading inputs for you .

Input

The input starts with two integers A_length and B_length (1 <= A_length, B_length <= 300,000), indicating list A's length and list B's length.

Then, there are two lines. The first line includes the elements in list A, and the second line includes the elements in list B.
Note, there might be multiple sets of lists A and B for you to merge into C in the input.

For example:

4 5

1 2 3 4

5 6 7 8 9

1 1

2

2

First two integers: 4 5 indicate that numbers of elements in lists A and B are 4 and 5, respectively.  The following two lines are the elements in the two lists, respectively.
The 4th line indicates that there is only 1 number in each list of A and B, which are both 2.

Output

Print every element in the list C, separated by “->”.

You need to output '\n' at the end of the line.

(newline)

For example,

1->2->3->4->5->6->7->8->9

2->2

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

12037.cpp

Partial Judge Header

12037.h

Tags

Discuss