Merge two sorted linked list in java

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