Node * merge(Node*h1, Node*h2){
if(h1 == NULL) return h2; // 如果一个链表为空,则返回另一个链表
if(h2 == NULL) return h1;
Node* head = NULL; // 合并后的头结点
Node* tail = NULL; // 合并后的尾结点
if(h1->data < h2->data){ // 确定合并后的头结点
head = h1;
h1 = h1->next;
}else{
head = h2;
h2 = h2->next;
}
tail = head; // 将tail指向head
while(h1 && h2){ // 遍历两个链表,找到最小值节点,并加入新链表中
if(h1->data < h2->data){
tail->next = h1;
tail = tail->next;
h1 = h1->next;
}else{
tail->next = h2;
tail=tail->next;
h2=h2->next;
}
}
if(h1 != NULL) // 将未遍历完的剩余节点加入新链表中
tail -> next=h1;
if(h2 !=NULL)
tail -> next=h2;
return head; // 返回合并后的头结点
}