import java.util.*;
class LinkedList {
private class Node {
int data;
Node next;
}
private Node head;
private Node tail;
private int size;
public int getFirst() throws Exception {
if (this.size == 0)
throw new Exception("linked list is empty");
return head.data;
}
public int getLast() throws Exception {
if (this.size == 0)
throw new Exception("linked list is empty");
return tail.data;
}
public void addLast(int item) {
// create a new node
Node nn = new Node();
nn.data = item;
nn.next = null;
// update summary
if (size == 0) {
this.head = nn;
this.tail = nn;
size++;
} else
{
this.tail.next = nn;
this.tail = nn;
size++;
}
}
public void addFirst(int item) {
Node nn = new Node();
nn.data = item;
nn.next = null;
if (size == 0) {
this.head = nn;
this.tail = nn;
size++;
} else {
nn.next = this.head;
this.head = nn;
size++;
}
}
public int removeFirst() throws Exception {
Node fn = this.head;
if (this.size == 0)
throw new Exception("linked list is empty");
if (this.size == 1) {
this.head = null;
this.tail = null;
size = 0;
} else {
Node np1 = this.head.next;
this.head = np1;
size--;
}
return fn.data;
}
private Node getNodeAt(int idx) throws Exception {// we make it private as we dont want client class to access
// it
// and get node address
if (this.size == 0) {
throw new Exception(“LL is empty”);
}
if (idx < 0 || idx >= this.size) {
throw new Exception(“Invalid Index”);
}
Node temp = this.head;
for (int i = 1; i <= idx; i++) {
temp = temp.next;
}
return temp;
}
public void addAt(int item, int idx) throws Exception {
if (idx < 0 || idx > size) {
throw new Exception("Invalid Index.");
}
if (idx == 0) {
addFirst(item);
} else if (idx == this.size) {
addLast(item);
} else {
// create a new node
Node nn = new Node();
nn.data = item;
nn.next = null;
// attach
Node nm1 = getNodeAt(idx - 1);
Node np1 = nm1.next;
nm1.next = nn;
nn.next = np1;
// summary update
this.size++;
}
}
public void merge_sorted_list(LinkedList other) throws Exception {
// write your code here
int i = 0;
Node t1 = this.head;
Node t2 = other.head;
while (t1 != null && t2 != null) {
if (t1.data > t2.data) {
addAt(t2.data,i);
t2 = t2.next;
i++;
}else {
t1 = t1.next;
i++;
}
}
}
public void display() {
Node temp = this.head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
static Scanner scn = new Scanner(System.in);
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
int t = scn.nextInt();
while(t > 0){
LinkedList list1 = new LinkedList();
int n1 = scn.nextInt();
for (int j = 0; j < n1; j++) {
int item = scn.nextInt();
list1.addLast(item);
}
LinkedList list2 = new LinkedList();
int n2 = scn.nextInt();
for (int j = 0; j < n2; j++) {
int item = scn.nextInt();
list2.addLast(item);
}
list1.merge_sorted_list(list2);
list1.display();
t--;
}
}
}
