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

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

#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;
}