输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则

/*
输入两个单调递增的链表，输出两个链表合成后的链表，
当然我们需要合成后的链表满足单调不减规则。
/
/
下面有两种方法，
第一个：是将两个链表各节点的数据存入一个数组，然后进行数组排序，在建立一个新的链表
把数组元素存入链表
第二个：是直接建立一个ListNode* h = new ListNode* (-1);链表，然后通过标胶链表1和链表2节点数据的大小，
把大的数据优先存入新链表。
*/

/*
struct ListNode {
int val;
struct ListNode next;
ListNode(int x) :
val(x), next(NULL) {
}
};/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode* p=(ListNode)malloc(sizeof(ListNode));
p->next=NULL;
ListNode x=p;
if(pHead1==NULL&&pHead2!=NULL)
{
return pHead2;
}
else if(pHead1!=NULL&&pHead2==NULL)
{
return pHead1;
}
else if(pHead1==NULL&&pHead2==NULL)
{
return nullptr;
}
vector<int> array;
while(pHead1!=NULL||pHead2!=NULL)
{
array.insert(array.end(),pHead1->val);
array.insert(array.end(),pHead2->val);
if(pHead1!=NULL)
{
pHead1=pHead1->next;
}
if(pHead2!=NULL)
{
pHead2=pHead2->next;
}
}
int i,j,size=array.size(),temp;
for(i=0;i<size;i++)
{
for(j=0;j<size-i-1;j++)
{
if(array[j]>array[j+1])
{
temp=array[j+1];
array[j+1]=array[j];
array[j]=temp;
}
}
}
for(i=0;i<size;i++)
{
p->val=array[i];
if(i!=size-1)
{
p->next=(ListNode*)malloc(sizeof(ListNode));
p=p->next;
p->next=NULL;
}
}
return x;
}
};</int>

public class Solution {
public ListNode* Merge(ListNode* list1,ListNode* list2) {
ListNode* h = new ListNode(-1);
ListNode cur = h;
while(list1 != null && list2 !=null){
if(list1.val<=list2.val){
cur.next = list1;
list1 = list1.next;
}else{
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
if(list1!=null) cur.next = list1;
if(list2!=null) cur.next = list2;
return h.next;
}
}