typedef int DataType;

 //建立链表

 class Link

 {

 private:

     struct Node

     {

         DataType data;

         Node *next;

     };

     Node *head; //哨兵位

 public:

     Link()

     {

         Init();

     }

     ~Link()

     {

         Delete();

     }

     void Init()

     {

         head = new Node;

         head->next = NULL;

     }

     void Delete()

     {

         for (Node *p = head; p != NULL;)

         {

             Node *pTemp = p->next;

             delete p;

             p = pTemp;

         }

         head = NULL;

     }

     bool Empty()

     {

         return head->next == NULL;

     }

     void Print()

     {

         for (Node *p = head->next; p != NULL; p = p->next)

         {

             cout << p->data << endl;

         }

     }

     //顺序插入 考虑两种情况 1.空表 2.当插入值是最大值的时候

     void SortInsert(DataType data)

     {

         Node *p = head;

         do

         {

             if (p->next == NULL || p->next->data > data)

             {

                 Node *pNew = new Node;

                 pNew->data = data;

                 pNew->next = p->next;

                 p->next = pNew;

                 return;

             }

             p = p->next;

         } while (true);

     }

     //使用数组初始化列表

     void ArrayInsert(DataType array[], int size)

     {

         for (int i=; i<size; ++i)

         {

             SortInsert(array[i]);

         }

     }

     //尾插法直接插入

     void Insert(DataType data)

     {

         Node *p = head;

         while(p->next != NULL)

         {

             p = p->next;

         }

         Node *pNew = new Node;

         pNew->data = data;

         pNew->next = NULL;

         p->next = pNew;

     }

     //去掉首结点并返回首结点的值

     int ExtractDate()

     {

         if (! Empty())

         {

             DataType data = head->next->data;

             Node *p = head->next;

             Node *pFirst = p->next;

             delete p;

             p = NULL;

             head->next = pFirst;

             return data;

         }

         return -;

     }

     int GetData()

     {

         if (!Empty())

         {

             return head->next->data;

         }

     }

     bool Find(const DataType data)

     {

         for (Node *p = head->next; p != NULL; p = p->next)

         {

             if (p->data == data)

             {

                 return true;

             }

         }

         return false;

     }

     void Swap(Link &p)   //交换两个链表主要是交换 head

     {

         if (head != p.head)

         {

             Node *tmp = head->next;

             head->next = p.head->next;

             p.head->next = tmp;

         }

     }

 };

 //保持最小堆性质 参数inode为内部结点 注意结点从1开始，数组从0开始

 void MinHeapify(int array[], int size, int inode)

 {

     int least= inode;                //父结点

     int left = inode*;                //左子结点

     int right = inode*+;            //右子结点

     if (left <= size && array[left-] < array[least-])

     {

         least = left;

     }

     if (right <= size && array[right-] < array[least-])

     {

         least = right;

     }

     if (least != inode)                    //父结点小于 左子结点 或者 右子结点

     {

         int temp = array[inode-];            //子结点值与父结点值交换

         array[inode-] = array[least-];

         array[least-] = temp;

         MinHeapify(array, size, least);      //再次验证被交换的值的子结点是否满足 最小堆性质

     }

 }

 //建立最小堆 使每一个父结点小于子结点

 void BuildMinHeap(int array[],int size)

 {

     for(int i=size/; i>; --i)     //最多有 size/2 个内部结点

     {

         MinHeapify(array, size, i);

     }

 }

 //k个已排好序的链表合并为一个链表

 //pLink 链表数组的地址, linkSize链表数组的大小, array 数组的地址, count数组的大小

 void SortLink(Link *pLink, int linkSize, Link *link)

 {

     int *pArray = new int[linkSize]; //动态分配k个大小的数组

     for (int i=; i<linkSize; ++i)    //从k个链表中取首结点的值

     {

         pArray[i] = pLink[i].GetData();

     }

     int j=;

     do

     {

         BuildMinHeap(pArray,linkSize); //构造最小堆，即每个父结点小于或等于子结点，根结点为最小值

         for (j=; j<linkSize; ++j)

         {

             if(pLink[j].Find(pArray[]))   //寻找最小值来自于哪一个链表

             {

                 link->Insert(pLink[j].ExtractDate());  //去掉并返回链表的的值（更新链表）

                 break;

             }

         }

         if (!pLink[j].Empty())  //确保取出值的链表不为空

         {

             pArray[] = pLink[j].GetData();   //更新数组

         }

         else

         {

             pArray[] = pArray[linkSize-];

             pLink[j].Swap(pLink[linkSize-]);  //交换两个链表

             --linkSize;

         }

     } while (linkSize != );

     delete [] pArray;

 }

 void main()

 {

     //检测是否有内存泄露 需要加头文件#include <crtdbg.h>

     _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

     Link k[];

     int Array[][] = { {, , , , },

                         {, , , , },

                         {, , , , },

                         {, , , , },

                         {, , , , }};

     for (int i=; i<; ++i)

     {

         k[i].ArrayInsert(Array[i],sizeof(Array[i])/sizeof(Array[i][]));

     }

     //for (int i=0; i<5; ++i)

     //{

     //    k[i].Print();

     //}

     Link link;

     SortLink(k, sizeof(k)/sizeof(k[]), &link);

     link.Print();

     system("pause");

 }