不使用额外空间,将A,B两链表的元素交叉归并

时间：2009-08-20 来源：ubuntuer

这个题目应该不是考什么算法,考数据结构了

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

#define N 5

typedef struct list
{
  int num;
  struct list* next;
}LIST;

void init_list(LIST** L)
{
  *L = (LIST*)malloc(sizeof(LIST));
  (*L)->next = NULL;
}

void add_list(LIST* L, int num)
{
  LIST* p = (LIST*)malloc(sizeof(LIST));
  p->num = num;
  p->next = L->next;
  L->next = p;
}

void print_list(LIST* L)
{
  LIST* p = L->next;
  while(p!=NULL)
   {
    printf("%d\t", p->num);
    p = p->next;
   }
  printf("\n");
}

LIST* merge(LIST* L1, LIST* L2)
{
  LIST* L = L1;

  LIST* p1 = L1->next;
  LIST* p2 = L2->next;
  LIST* q1;
  LIST* q2;

  while(p1!=NULL&&p2!=NULL)
   {
     q1 = p1;
     p1 = p1->next;
     q1->next = p2;

     q2 = p2;
     p2 = p2->next;
     q2->next = p1;
   }
  return L;
}

int main(int argc, char *argv[])
{
  int i = 0;
  int num = 0;
  srand((unsigned int)time(NULL));

  LIST* L1 = NULL;
  LIST* L2 = NULL;

  init_list(&L1);
  init_list(&L2);

  for(i=0;i<N;i++)
   {
     num = rand()%100+1;
     add_list(L1, num);
   }

  for(i=0;i<N;i++)
   {
     num = rand()%100+1;
     add_list(L2, num);
   }

  printf("list1 is:\n");
  print_list(L1);
  printf("list2 is:\n");
  print_list(L2);

  LIST* L = merge(L1,L2);
  printf("list is:\n");
  print_list(L);

  system("PAUSE");
  return 0;
}

上面那个代码有点问题,如果L2比L1长的话,错误就出来了!!!!刚实验室一哥们找到一递归的方法,perfect!!!可怜我想不到啊

LIST* merge(LIST* L1,LIST* L2)

{

if(L1==NULL)

return L2;

else

L1->next = merge(L2,L1->next);

return L1;

}

简洁,了当就是有点不好理解!!!!其实递归就是考虑一种情况时的状况就可以了.... L1 --- L11 --- L111 --- NULL L2 --- L22 --- L222 --- NULL 从最前面开始考虑: 如果L1==null的话直接return L2 merge(L1,L2) => L1->next = merge(L2,L1->next) ok对感叹就这么easy

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

#define N 5

typedef struct list
{
  int num;
  struct list* next;
}LIST;

void init_list(LIST** L)
{
  *L = (LIST*)malloc(sizeof(LIST));
  (*L)->next = NULL;
}

void add_list(LIST* L, int num)
{
  LIST* p = (LIST*)malloc(sizeof(LIST));
  p->num = num;
  p->next = L->next;
  L->next = p;
}

void print_list(LIST* L)
{
  LIST* p = L->next;
  while(p!=NULL)
   {
    printf("%d\t", p->num);
    p = p->next;
   }
  printf("\n");
}

LIST* merge(LIST* L1, LIST* L2)
{
  LIST* L = L1;

  LIST* p1 = L1->next;
  LIST* p2 = L2->next;
  LIST* q1;
  LIST* q2;

  while(p1!=NULL&&p2!=NULL)
   {
     q1 = p1;
     p1 = p1->next;
     q1->next = p2;

     q2 = p2;
     p2 = p2->next;

     if(p1!=NULL)
       q2->next = p1;
   }
   if(p1==NULL)
    q1->next = q2;

  return L;
}

LIST* merge1(LIST* L1, LIST* L2)
{
  if(L1==NULL)
    return L2;
  else
    L1->next = merge1(L2, L1->next);

   return L1;
}

int main(int argc, char *argv[])
{
  int i = 0;
  int num = 0;
  srand((unsigned int)time(NULL));

  LIST* L1 = NULL;
  LIST* L2 = NULL;

  init_list(&L1);
  init_list(&L2);

  for(i=0;i<N-2;i++)
   {
     num = rand()%100+1;
     add_list(L1, num);
   }

  for(i=0;i<N;i++)
   {
     num = rand()%100+1;
     add_list(L2, num);
   }

  printf("list1 is:\n");
  print_list(L1);
  printf("list2 is:\n");
  print_list(L2);

  #if 0
  LIST* L = merge(L1,L2);
  printf("list is:\n");
  print_list(L);
  #endif

  #if 1
  L1->next = merge1(L1->next,L2->next);
  printf("list is:\n");
  print_list(L1);
  #endif

  system("PAUSE");
  return 0;
}