欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

合并有序链表

程序员文章站 2022-05-23 09:17:46
...

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

/**
 * 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;
}