Merge sorted linked list

#1

Could someone please help me with the logic of this Problem Statement?

#2

Hi @dktrip,
The way we use to sort in merge sort we have to use the same concept to the sort the given two sorted linked list … Like the example case given 1 3 5 7 and 2 4 6 we will compare 1 of first list with 2 of second list and then take 1 from the first list as it is smaller and then shift the pointer to 3 and then compare 3 with 2 of second list and so on till one of the list reaches the end and then we will copy the remaining element to the final list as it is.

#3
#4

check the comment in the following program.

The .next you used is not correct as head should be checked and if you check head.next you skip the last element of the list

#5

Which next are you talking about?

#6

Now it says there is some error run time error.

#7

Did you look for comments in the code i have attached and matched it with your code .I have done changes in the lines i have added a comment into.There are //removed .next comment added in this program . Compare that line with the code you wrote.

#8

It is still showing errors to me. Please check out if possible. I have attached the code link below.

#9

Hey , I cannot open the link you provided . It shows some warning .can you just save the code and then send a proper link to the code .Thanks .

#10
#11

This is the code that I have written on the ide and on the hackerblocks but still it shows some error.

#12

The error is not in my code but in the main function that i have not written.

#13
#14

try this out. I just saved the code.

#15

Still can’t open .I think there is a problem with ide . Just copy and paste code in reply. I’ll check that

#16

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 { LinkedList list=new LinkedList(); while(this.head!=null && other.head!=null){ if (this.getFirst()<=other.getFirst()){ list.addLast(this.getFirst()); this.head=this.head.next; } else{ list.addLast(other.getFirst()); other.head=other.head.next; } } while(this.head.next!=null){ list.addLast(this.getFirst()); this.head=this.head.next; } while(other.head.next!=null){ list.addLast(other.getFirst()); other.head=other.head.next; } list.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){ 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–; } } }

#17

Please tell me the error in this code of mine.

#18

Hi @dktrip,
There is a error in coding block server so i cannot send the code but in the second and third while loop of merge_sort function you have used this.head.next!=null please make this this.head!=null and also in the third while loop make other.head!=null and your code will run .And i will reply as soon as server starts responding and i can save the code and then i’ll send the code also

#19

Hey dktrip ,
I checked the code you attached and it is working fine for me . I think earlier there was a error in online ide so you may be facing problems but it is all ok now . If you still have issue ,please reply.

#20

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.