不另开空间实现两个有序表合并_不使用额外空间合并两个有序表

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
  int data;
  struct node *next;
}*Listlink;

/*后插法创建单链表*/
void last_create(Listlink *head,int n)
{
  int i;
  Listlink p,q;
  *head=(Listlink)malloc(sizeof(struct node));
  (*head)->next=NULL; /*建立头结点*/
  q=*head;
  for(i=0;i<n;i++)
  {
    p=(Listlink)malloc(sizeof(struct node));
 scanf("%d",&(p->data));
 
 p->next=q->next;
 q->next=p;
 q=p;
  }
}

/*将两个递增单链表合并为一个递增的单链表*/
void merge(Listlink la,Listlink lb,Listlink *lc)
{
  Listlink pa,pb,pc;
  *lc=la;  /*合并后的链表头结点使用a链表的*/
 
  pa=la->next;
  pb=lb->next;
  pc=*lc;
 
  while(pa != NULL && pb != NULL)
  {
    if(pa->data<pb->data)
 {
   pc->next=pa;
   pa=pa->next;
   pc=pc->next;
 }
 else
 {
   pc->next=pb;
   pb=pb->next;
   pc=pc->next;
 }
 if(pa != NULL)
   pc->next=pa;
 else
   pc->next=pb;
  }
}

void print_list(Listlink head)
{
  Listlink p;
  p=head->next;
  while(p != NULL)
  {
    printf("%d ",p->data);
 p=p->next;
  }
}

int main()
{
  Listlink la,lb,lc;
 
  puts("houcha:");
  last_create(&lb,10);
  puts("houcha:");
  last_create(&la,10);
 
  merge(la,lb,&lc);
  print_list(lc);
  printf("/n");
 
 
  return 0;
}