Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list.
Input
The format for input is as follows:
The first line contains an integer n, the length of the first linked list.
The next line contains n integers, the elements of the first linked list.
The next line contains an integer m, the length of the second linked list.
The next line contains m integers, the elements of the second linked list.
Constraints:
0 <= n,m <= 1000
1 <= list[i] <= 10000, where list[i] is the ith element of the list.
Output
Print the merged sorted linked list in new line.
Example
Input:
3 1 2 3 2 3 4
Output:
1 2 3 3 4
Explanation:
The first linked list is: 1->2->3->NULL The second linked list is: 3->4->NULL Hence, the merged linked list is: 1->3->3->4->7->NULL
Input:
4 2 4 6 9 3 1 7 8
Output:
1 2 4 6 7 8 9
Explanation:
The first linked list is: 2->4->6->9->NULL The second linked list is: 1->7->8->NULL Hence, the merged linked list is: 1->2->4->6->7->8->9->NULL
Solution:–
import java.util.*; import java.lang.*; import java.io.*; class Node{ int data; Node next=null; Node(int data) { this.data=data; } } public class Main { static Node headOne=null; static Node headTwo=null; static Node dummy = new Node(0); static void insertionOne(int data) { Node newNode = new Node(data); if(headOne==null) { headOne=newNode; return; } Node temp=headOne; while(temp.next!=null) { temp=temp.next; } temp.next=newNode; } static void insertionTwo(int data) { Node newNode = new Node(data); if(headTwo==null) { headTwo=newNode; return; } Node temp=headTwo; while(temp.next!=null) { temp=temp.next; } temp.next=newNode; } static void combine() { Node prev=dummy; Node temp1=headOne; Node temp2=headTwo; while(temp1!=null && temp2!=null) { if(temp1.data < temp2.data) { prev.next=temp1; prev=temp1; temp1=temp1.next; } else{ prev.next=temp2; prev=temp2; temp2=temp2.next; } } while(temp1!=null) { prev.next=temp1; break; } while(temp2!=null) { prev.next=temp2; break; } } static void printList() { Node temp=dummy.next; while(temp!=null) { System.out.print(temp.data+" "); temp=temp.next; } } public static void main (String[] args) throws java.lang.Exception { //your code here Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for(int i=0;i<n;i++) { int val=sc.nextInt(); insertionOne(val); } int m = sc.nextInt(); for(int i=0;i<m;i++) { int val=sc.nextInt(); insertionTwo(val); } combine(); printList(); } }
Add a Comment