合并有序链表
程序员文章站
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;
}