题目描述:
代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* p=list1;
struct ListNode* q=list2;
struct ListNode* newHead=NULL;
struct ListNode* tail=NULL;
if(p!=NULL&&q!=NULL)
{
//先让newHead指向两个链表中第一个较小的节点
if(p->val<=q->val)
{
newHead=p;
p=p->next;
}
else
{
newHead=q;
q=q->next;
}
//让tail指向链表尾部
tail=newHead;
//逐个比较,逐个插入到新链表
while(p&&q)
{
if(p->val<=q->val)
{
tail->next=p;
p=p->next;
}
else
{
tail->next=q;
q=q->next;
}
tail=tail->next;
}
//第一个链表还有剩余
if(p)
{
tail->next=p;
}
else //第二个链表还有剩余
{
tail->next=q;
}
return newHead;
}
else 如果某个链表为空,就返回另一个
{
if(p==NULL)
{
return q;
}
else
{
return p;
}
}
}
思路:
先找出两个链表中第一个较小的结点,作为新链表的初始结点,然后开始逐个遍历,将当前最小值插入到新链表中,注意有一个链表为空的情况。