Merge 2 List all test cases failing

#1

import java.util.*;
class Main {

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(Main 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){

		    Main list1 = new Main();
		    int n1 = scn.nextInt();
		 
		    for (int j = 0; j < n1; j++) {
			    int item = scn.nextInt();
			    list1.addLast(item);
		}

            Main list2 = new Main();
		    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--;
        }
	
}

}

#2

for test case like:
4
2
1 1
2
1 1
3
1 2 3
3
4 5 6
4
1 2 3 4
0
2
1 1
2
-1 2

the correct answer should be :
1 1 1 1
1 2 3 4 5 6
1 2 3 4
-1 1 1 2

#3

The Approach is pretty simple that we will Start from the head of the two lists and consume that element from the two of the Lists first which is smaller and add that element into the ans list. After consuming, Advance the iterator to point to the next node in the list. The size of the Lists can be different so after consuming elements simultaneously from the two list, We need to check if any of the two list is empty, and add the elements of that list as it is in the answer List.
see this :

#4

Thank you! :slight_smile:

#5

please mark your doubts as resolved :slight_smile: