题目:输入两个递增的排序的链表,合并这两个链表并使新链表中的节点仍然是
按照递增排序的。例如链表1链表2合并为链表3.
List1:->->-> List2:->->-> List3:->->->->->->->
链表结点定义如下:
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
}
其实我们可以简单梳理下流程如下:
1.两个指针分别指向List1和List2的头结点。设为ptr1和ptr2
2.比较ptr1和ptr2结点的值,ptr1<ptr2则ptr1则是合并后的链表头结点
3.ptr1向后移动一个结点此时再比较 ptr1>ptr2则将ptr2的节点插入到头结点之后
4.当ptr1或者ptr2到达末尾时 比如ptr1到达List1结尾后 若此时ptr2还未到List2结尾
将ptr2插入到新排序的链表后面.
代码实现如下:
#include <iostream>
using namespace std; struct ListNode
{
int data;
struct ListNode *next;
}; struct ListNode* CreateList()
{
struct ListNode* Head,*p;
Head=(struct ListNode*)malloc(sizeof(ListNode));
Head->data=;
Head->next=NULL;
p=Head; cout<<"Create List....(0-exit!)"<<endl;
while(true)
{
int Data;
cin>>Data;
if(Data!=)
{
struct ListNode* NewNode;
NewNode=(struct ListNode*)malloc(sizeof(ListNode));
NewNode->data=Data;
NewNode->next=NULL;
p->next=NewNode;
p=p->next;
}
else
{
break;
}
} return Head->next;
} void PrintList(struct ListNode* Head)
{
cout<<"The List is: "; struct ListNode *p;
p=Head;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
} struct ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
{
if(pHead1==NULL&&pHead2==NULL)
return NULL; if(pHead1==NULL&&pHead2!=NULL)
return pHead2; if(pHead1!=NULL&&pHead2==NULL)
return pHead1; struct ListNode *ptr1,*ptr2,*MergeList,*newhead;; ptr1=pHead1;
ptr2=pHead2; if(ptr1->data>ptr2->data)
{
MergeList=ptr2;
ptr2=ptr2->next;
}
else
{
MergeList=ptr1;
ptr1=ptr1->next;
} newhead=MergeList; while(ptr1!=NULL&&ptr2!=NULL)
{
if(ptr1->data>ptr2->data)
{
MergeList->next=ptr2;
ptr2=ptr2->next;
MergeList=MergeList->next;
} if(ptr1->data<ptr2->data)
{
MergeList->next=ptr1;
ptr1=ptr1->next;
MergeList=MergeList->next;
}
} if(ptr1!=NULL)
{
while(ptr1!=NULL)
{
MergeList->next=ptr1;
ptr1=ptr1->next;
MergeList=MergeList->next;
}
MergeList->next=NULL;
}
if(ptr2!=NULL)
{
while(ptr2!=NULL)
{
MergeList->next=ptr2;
ptr2=ptr2->next;
MergeList=MergeList->next;
}
MergeList->next=NULL;
} return newhead;
} int main()
{
ListNode *List1,*List2,*MergeList;
List1=CreateList();
PrintList(List1);
List2=CreateList();
PrintList(List2);
MergeList=Merge(List1,List2);
PrintList(MergeList);
return ;
}
运行截图: