[数据结构与算法]合并有序链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* create_node(int num)
{
    struct ListNode* ret=calloc(1,sizeof(struct ListNode));
    ret->next=NULL;
    ret->val= num;
    return ret;
}

int head_delete(struct ListNode *head)
{
    struct ListNode*p= head->next;
    int ret=p->val;
    head->next=p->next;
    free(p);
    return ret;
}

/*void add_tail(struct ListNode* head)
{
    struct ListNode&* p=head;
    while(p->next)
    {
        p=p->next;
    }

}*/

void insert(struct ListNode* node,struct ListNode* new_node)
{
    struct ListNode*tmp=node->next;
    node->next=new_node;
    new_node->next=tmp;
    return;
}

void search_insert(struct ListNode* p1,struct ListNode* new_node,int num)
{
            while(1)
        {
            if(num>=p1->val&&p1->next==NULL||num>=p1->val&&num<=p1->next->val)
            {
                insert(p1,new_node);
                break;
            }
                p1=p1->next;   
        }
        return;
}

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1==NULL)
    return l2;
    if(l2==NULL)
    return l1;
    //struct ListNode* p1=l1;
    struct ListNode* p2=l2;
    while(p2->next!=NULL)
    {
        int num= head_delete(l2);
        struct ListNode* p1=l1;
        if(num<l1->val)
        {
        int tmp1=l1->val;
        l1->val=num;
        num=tmp1;
        struct ListNode* new_node=create_node(num);
        insert(l1,new_node);
        }
        else
        {
        struct ListNode* new_node=create_node(num);
        search_insert(p1,new_node,num);
        }
    }
    int first=l2->val;
     if(first<l1->val)
        {
        int tmp1=l1->val;
        l1->val=first;
        first=tmp1;
        struct ListNode* new_node=create_node(first);
        insert(l1,new_node);
        }
        else{
                struct ListNode* new_node2=create_node(first);
                search_insert(l1,new_node2,first);
            }
    return l1;
}