合并链表排序

 

#include "stdafx.h"
#include "stdlib.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif



typedef struct _node
{
 int date;
 struct _node* next;
} Node, *NodeList;

NodeList creat_list_1()
{
 NodeList head, pCurr, pPrev;
 head = (NodeList)malloc(sizeof(Node));
 pPrev = head;
 for (int i = 0; i < 3; i++)
 {
  pCurr = (NodeList)malloc(sizeof(Node));
  pCurr->date = 2*i + 3;
  pPrev->next = pCurr;
  pPrev = pCurr;
 }
 pCurr->next = NULL;

 return head;
}
NodeList creat_list_2()
{
 NodeList head, pCurr, pPrev;
 head = (NodeList)malloc(sizeof(Node));
 pPrev = head;
 for (int i = 0; i < 3; i++)
 {
  pCurr = (NodeList)malloc(sizeof(Node));
  pCurr->date = 2*i + 2;
  pPrev->next = pCurr;
  pPrev = pCurr;
 }
 pCurr->next = NULL;

 return head;
}

void print_list(NodeList head)
{
 NodeList pCurr = head->next;
 while(pCurr)
 {
  printf("%d\n", pCurr->date);
  pCurr = pCurr->next;
 }
}

NodeList union_list(NodeList la, NodeList lb) //合并两链表 并排序
{
 NodeList pa, pb, r;
 pa = la->next; pb = lb->next;
 la->next = NULL; lb->next = NULL;
 while (pa && pb)
 {
  if (pa->date <= pb->date)
  {
   r = pa->next;
   pa->next = la->next;
   la->next = pa;
   pa = r;
  }
  else
  {
   r = pb->next;
   pb->next = la->next;
   la->next = pb;
   pb = r;
  }
 }
 while (pa)
 {
  r = pa->next;
  pa->next = la->next;
  la->next = pa;
  pa = r;
 }
 while (pb)
 {
  r = pb->next;
  pb->next = la->next;
  la->next = pb;
  pb = r;
 }
 return la;
}

int _tmain(int argc, _TCHAR* argv[])
{
 NodeList p1, p2;
 p1 = creat_list_1();
 p2 = creat_list_2();
 print_list(p1);
 print_list(p2);
 union_list(p1, p2);
 printf("\n");
 print_list(p1);
// print_list(p2);

 return 0;
}