1.设计算法将两个递增的有序链表合并为一个递增的有序链表。

type

  point=^node;

  node=record

         data:integer;

         next:point;

       end;

var h1,h2,h:point;

procedure prt(p:point); //打印链表

begin

  p:=p^.next;

  while p<>nil do

  begin

    write(p^.data,' ');

    p:=p^.next;

  end;

  writeln;

end;

procedure creat(var h:point); //建立链表

var x:integer; p,q:^node;

begin

  writeln('请输入升序的数，负数结束：');

  new(h);

  p:=h;

  read(x);

  while(x>=0)do

  begin

    new(q);

    q^.data:=x;

    p^.next:=q;

    p:=q;

    read(x);

  end;

  p^.next:=nil;

end;

function merge_link(var p,q:point):point; //升序合并二个升序链表

var h,w:^node;

begin

  w:=p; p:=p^.next; dispose(w); //回收一个头结点，p指向首个数据结点

  w:=q; h:=q; q:=q^.next; //h:合并后的头结点，q指向首个数据结点

  while (p<>nil)and(q<>nil) do //当二个链表都不空时

    if(p^.data

    begin

      w^.next:=p; //把小结点链入

      p:=p^.next; //跳过此结点

      w:=w^.next; //w指向当前合并后链表的尾结点

    end

    else

    begin //下面三行作用同上

      w^.next:=q;

      q:=q^.next;

      w:=w^.next;

    end;

  if p<>nil then w^.next:=p; //将未完的链表接入

  if q<>nil then w^.next:=q; //将未完的链表接入

  merge_link:=h; //返回合并后的链表头指针

end;

begin

  creat(h1);

  creat(h2);

  h:=merge_link(h1,h2);

  writeln('合并后的链表：');

  prt(h);

end.

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)

{

//合并链表La和Lb，合并后的新表使用头指针Lc指向

pa=La->next;

pb=Lb->next;    

//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点

Lc=pc=La;  //用La的头结点作为Lc的头结点

while(pa && pb)

{

if(pa->datadata){

pc->next=pa;

pc=pa;

pa=pa->next;

}

//取较小者La中的元素，将pa链接在pc的后面，pa指针后移

else if(pa->data>pb->data) {

pc->next=pb;

pc=pb; 

pb=pb->next;

}

//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移

else //相等时取La中的元素，删除Lb中的元素

{

pc->next=pa;

pc=pa;

pa=pa->next;

q=pb->next;

delete pb ;

pb =q;

}

}

pc->next=pa?pa:pb;    //插入剩余段

delete Lb;            //释放Lb的头结点

node *mergelink(node *p, node *q)
{
node *h, *r;
h = (node*) malloc (sizeof(node));
h->next = NULL;
r = h;
while (p != NULL && q != NULL)
{
if (p->data <= q->data)
{
r->next = p;
r = p;
p = p->next;
}
else
{
r->next = q;
r = q;
q = q->next;
}
}

if (p == NULL)
r->next = q;
if (q == NULL)
r->next = p;

p = h->next;
h = h->next;
free(p);
return h;
}