链表合并先，将两个链表排序，在合并的时候引入一个内存泄露的问题，之后会继续讨论。

#include <ctime>

#include <cstdlib>

#include <iostream>

#include <cstdio>

using namespace std;

#define NN

#define RANGE 100

#define NUM 10

struct node

{

 int value;

 node * next;

 node(int v = -1, node *nxt = NULL) : value(v),next(nxt){}

};

node * make_link();

void display(node *);

void sort(node *);

node * merge(node *,node *);

void mem_realse(node *);

int get_rand()

{

    return rand() % RANGE;

}

node *mcur_;

int main()

{

 node* head1 = make_link();

 display(head1);

 sort(head1);

 node* head2 = make_link();

 display(head2);

 sort(head2);

    node *head = merge(head1,head2);

 display(head);

 mem_realse(head);

 delete mcur_;

 return 0;

}

node * make_link()

{

 node *head = new node();//没有表头

 node *cur = head;

 srand( time(NULL) );

 for(int i= 0; i < NUM - 1; i++)

 {

  cur->value = rand() % RANGE;

  cur->next = new node();

  cur = cur->next;

  cur->next = NULL;

 }

 cur->value = rand() % RANGE;//最后一个数

 return head;

}

void display(node *head)

{

 node *cur = head;

 int nodeNum = 0;

 while(cur)

 {

  cout << cur->value << " " ;

  nodeNum++;

  cur = cur->next;

 }

 cout << endl;

#ifdef NN

 cout << nodeNum<<endl;

#endif

}

void sort(node *head)

{

 node *cur = head;

 while(cur)                 //两重循环(每重循环维护一个当前指针)，每次从链表中找出一个值最小的结点，

 {                         //保存其指针，然后与当前第一个进行值互换

  node *min = cur;

  node *cur2 = cur->next;

  while(cur2)

  {

   if(cur2->value < min->value)

   {

    min = cur2;

   }

   cur2 = cur2->next;

  }

  int tem = cur->value;

  cur->value = min->value;

  min->value = tem;

  cur = cur->next;

 }

}

node * merge(node *h1,node *h2)   //O(1)的，需要一个辅助的结点，两个链表需要已经进行了排序

{                                 // 没次从两个链表中选出一个合适的来作为新链表的下一个结点

 node *mcur = new node();      // 辅助结点，不能仅仅是一个指针，next域需要发挥作用

 mcur_ = mcur;

 ///其实这个mcur是没有存储结点数据的，合并完之后造成了mcur不会指向一开始分配的这块内存区域

 ///造成这块区域的内存无法回收，所以使用了mcur_ 这个全局变量来保存该指针，最后来释放这块区域

 ///我以开始就意识到了，但是没有办法论证，接下来会有博客文章会借助Visual Studio的运行库函数来分析内存泄露问题

 node *cur1 = h1 , *cur2 = h2; //辅助结点始终指向“新链表”的当前结点，也可以说是最近一个加入该链表的结点

 while(cur1 && cur2)

 {

  if(cur1->value < cur2->value)

  {

   mcur->next = cur1;

   mcur = mcur->next;//mcur指向当前的cur1

   cur1 = cur1->next;//cur1已经处理，指向下一个

  }

  else

  {

   mcur->next = cur2;

   mcur = mcur->next;

   cur2 = cur2->next;

  }

 }

 if(cur1)

 {

  mcur->next = cur1;

 }else

 {

  mcur->next = cur2;

 }

 //cout << "mcur->value: "<< mcur->value <<endl;

 return h1->value < h2->value ? h1 : h2;//merge 函数其实只是将两个链表的指针进行了重新组织，并没有使用新的区域

}

void mem_realse(node *h)

{

 node *p = h;

 int count = 0;

 while(p)

 {

  h = p -> next;

  delete p;

  count++;

  p = h;

 }

 cout << "realse " << count << " node " <<endl;

}

很奇怪，在生成随机数的时候，两次make_link生成的数据时相同的，我已经加了srand(time(NULL))了。。。。