两个有序链表合并成一个有序链表解决思路

两个有序链表合并成一个有序链表

C/C++ code

struct node{    node* next;    int data;    node(){next=NULL;}    node(int val):data(val),next(NULL){}};struct list{    node* head;    list(){ head=new node();}    ~list() { Clear(); };    void AddItem(int data)    {        node* newNode=new node(data);        newNode->next=head->next;        head->next=newNode;    }    //................};

//list3是个带头结点的空链表，list1,list2均有头节点，而且都已经拍好序了
void Merge(list& list1, list& list2 ,list& list3)
{

}



[解决办法]
void Merge(list& list1, list& list2 ,list& list3)
{
list *pa,*pb,*pc;
pa = list1->next;
pb = list2->next;
pc = list1 = list2;
while(pa&&pb)
{
if (pa->data <= pb->data)
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
 while(pa)
 {
  pc->next = pa;
pc = pa;
pa = pa->next;
 }
 while(pb)
 {
  pc->next = pb;
pc = pb;
pb = pb->next;
 }

}
随便参考一下哈

查看更多 下一篇