Merge Two Sorted Linked List

#1

Its giving runtime erro but this code is passing all cases on hackerrank also but not on cb compiler please check.

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;
}

public void merge_sorted_list(LinkedList other) throws Exception {
	if(this.size<=0 || other.size<=0) {
		throw new Exception("LL is empty");
	}		
	// write your code here
	Node finalHead;
	Node finalTail;
	
	Node head1=this.head;
	Node head2=other.head;
	if(head1.data<=head2.data) {
		finalHead=head1;
		finalTail=head1;
		head1=head1.next;
	}else {
		finalHead=head2;
		finalTail=head2;
		head2=head2.next;
	}
	
	while(head1!=null && head2!=null) {
		if(head1.data<=head2.data) {
			finalTail.next=head1;
			finalTail=head1;
			head1=head1.next;
		}else {
			finalTail.next=head2;
			finalTail=head2;
			head2=head2.next;
		}
	}
	
	if(head1==null) {
		finalTail.next=head2;
	}else {
		finalTail.next=head1;
	}
	this.head=finalHead;
	
	display();
	
}

public void display() {

	Node temp = this.head;

	while (temp != null) {
		System.out.print(temp.data + " ");
		temp = temp.next;
	}

}

}
public class Main{

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);

        t--;
        }
	
}

}

#2

@Ritik488 Hi, you are missing the edge case, i have corrected your code, check the comments you will get it where you are going wrong.

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;
}

public void merge_sorted_list(LinkedList other) throws Exception {
	// If both lists are empty, then return
	if(this.size<=0 && other.size<=0) {
		return;
	}

	// If original list is empty, print second as it is
	if(this.size<=0) {
		other.display();
		System.out.println();
		return;
	}

	// If other list is empty, print original as it is
	if(other.size<=0) {
		this.display();
		System.out.println();
		return;
	}

			
	// write your code here
	Node finalHead;
	Node finalTail;
	
	Node head1=this.head;
	Node head2=other.head;
	if(head1.data<=head2.data) {
		finalHead=head1;
		finalTail=head1;
		head1=head1.next;
	}else {
		finalHead=head2;
		finalTail=head2;
		head2=head2.next;
	}
	
	while(head1!=null && head2!=null) {
		if(head1.data<=head2.data) {
			finalTail.next=head1;
			finalTail=head1;
			head1=head1.next;
		}else {
			finalTail.next=head2;
			finalTail=head2;
			head2=head2.next;
		}
	}
	
	if(head1==null) {
		finalTail.next=head2;
	}else {
		finalTail.next=head1;
	}
	this.head=finalHead;
	
	display();
	// New line after each test case
	System.out.println();
}

public void display() {

	Node temp = this.head;

	while (temp != null) {
		System.out.print(temp.data + " ");
		temp = temp.next;
	}

}

}
public class Main{

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);

        t--;
        }
	
}

}