## 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

```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

```

```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 dummy = new Node(0);

static void insertionOne(int data)
{
Node newNode = new Node(data);
{
return;
}

while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newNode;
}

static void insertionTwo(int data)
{
Node newNode = new Node(data);
{
return;
}

while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newNode;
}

static void combine()
{

Node prev=dummy;

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

}
}```