Merge Sorted LinkedList

#1

All the test cases are failed please correct me

#2

it compiles fine but unable to pass the test cases

#3

please help me out from this problem

#4

please give me the response

#5

@Amre-8800,
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.

Also create a new list for the answer. And return that list.

#6

thanks …but can you tell me where is the problem in my code .my approach is wrong ya right

#7

@Amre-8800,
You are not creating a new linkedlist buddy

#8

i am doing the same question by another approach but still i am unable to pass the test cases

#9

it compiles fine but not pass the test cases

#10

@Amre-8800,
Please share your code. Also is your code passing the sample test case?

#11

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

public static void merge_sorted_list(Main n1, Main n2) throws Exception {   

	// write your code here
	Main n3 = new Main();
	
	while(n1.size != 0 && n2.size != 0){   
		if(n1.getFirst() < n2.getFirst()){    
			n3.addLast(n1.getFirst());
			n1.removeFirst();
		}else{
			n3.addLast(n2.getFirst());
			n2.removeFirst();
		}
	}

	while(n1.size != 0){
		n3.addLast(n1.getFirst());
		n1.removeFirst();
	}
	while(n2.size != 0){
		n3.addLast(n2.getFirst());
		n2.removeFirst();
	}

	n3.display();
}

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);
		}
		  merge_sorted_list(list1,list2);

        t--;
        }
	
}

}

#12

here is my code please tell me the error

#13

@Amre-8800,
https://ide.codingblocks.com/s/241025 corrected code

Only error in your code was that you were not printing the output of a new input in a new line. :smile:

#14

@Amre-8800,
Hope this helps you. if you have any more doubts, feel free to reply on this thread. I will be happy to help you.

#15

thanks a lot for helping me… i don not understand where is my problem…but now its clear thanks a lot

1 Like