template <class Type> class ListNode {   //链表结点类的定义
  friend class List<Type>;      //List类作为友元类定义
  private:
     Type data;        //数据域
     ListNode<Type> *link;      //链指针域
  public:
     ListNode ( ) : link (NULL) { }    //仅初始化指针成员的构造函数
     ListNode ( const Type& item ) : data (item), link (NULL) { }
  //初始化数据与指针成员的构造函数
     ListNode<Type> * getNode ( const Type& item, ListNode<Type> *next = NULL )
                                    //以item和next建立一个新结点
   ListNode<Type> * getLink ( ) { return link; }  //取得结点的下一结点地址
   Type getData ( ) { return data; }    //取得结点中的数据
   void setLink ( ListNode<Type> * next ) { link = next; }  //修改结点的link指针
   void setData ( Type value ) { data = value; }  //修改结点的data值 
  };

程序是用C++的类模板实现的,主要有两个文件:主文件mail( )和头文件list.h
下面是程序的清单:
main.cpp文件清单:
#include <stdio.h>
#include <list.h>   //包含单链表数据类型和函数说明的头文件。
const int stop=-1;   //以-1作为建表过程的中止标志。
void main(  )
{

List<int> ha(stop);   //建立以ha为头结点的单链表，并以-1为中止建表标志。
ha.Browse( );       //打印浏览所建立的以ha为头结点的单链表
List<int> hb(stop);   //建立以hb为头结点的单链表，并以-1为中止建表标志。
hb.Browse( );       //打印浏览所建立的以ha为头结点的单链表
ha.Merge(hb);      //将以ha为头结点的单链表和以hb为头结点的单链表连接起来，
                  //连接后的单链表以ha为头结点。
ha.Browse( );       //打印浏览连接后的单链表
}
list.h头文件清单:
#include <iostream.h>      //包含输入输出的头文件
template <class Type> class List;   //单链表数据类型
template <class Type> class ListNode {  //单链表中数据元素的数据类型
friend class List<Type>;
public:
  ListNode ( );        //构造函数
ListNode ( const Type& item );    //构造函数
private:
  Type data;                       //单链表元素的数据域
  ListNode<Type> *link;            //单链表元素中的指针域
};

template <class Type> class List {
public:
List ( const Type finished );    //建立链表
  void Browse ( );       //打印链表
  void Merge ( List<Type> &hb );    //连接链表
private:
 ListNode<Type> *first, *last; //*first保存单链表的头结点，*last保存单链表的尾结点
};

//各成员函数的实现
 template <class Type>
ListNode<Type> :: ListNode ( ) : link ( NULL ) { }
 //构造函数, 仅初始化指针成员。

 template <class Type> ListNode<Type> :: ListNode ( const Type & item ) : data ( item ), link ( NULL ) { }
 //构造函数, 初始化数据与指针成员。

template <class Type> List<Type> :: List ( const Type finished ) {
//创建一个带表头结点的有序单链表, finished是停止建表输入标志, 是所有输入值中不可能出现的数值。
 first = last = new ListNode<Type>( );   //创建表头结点
  Type value; ListNode<Type> *p, *q, *s;
  cin >> value;
  while ( value != finished ) {     //循环建立各个结点
   s = new ListNode<Type>( value );
q = first;  p = first->link;
while ( p != NULL && p->data <= value )
{ q = p;  p = p->link; }   //寻找新结点插入位置
q->link = s;  s->link = p;    //在q, p间插入新结点
if ( p == NULL ) last = s;
cin >> value;
}
}

template <class Type> void List<Type> :: Browse ( ) {
//浏览并输出链表的内容
  cout<<"\nThe List is : \n";
  ListNode<Type> *p = first->link;
 while ( p != NULL ) {
   cout << p->data;
   if ( p != last ) cout << "->";
   else cout << endl;
   p = p->link;
  }
}

template <class Type> void List <Type> :: Merge ( List<Type>& hb) {
 //将当前链表this与链表hb按逆序合并，结果放在当前链表this中。
 ListNode<Type> *pa, *pb, *q, *p;
 pa = first->link;  pb = hb.first->link;   //检测指针跳过表头结点
first->link = NULL;      //结果链表初始化
while ( pa != NULL && pb != NULL ) {  //当两链表都未结束时
if ( pa->data <= pb->data )
 { q = pa;  pa = pa->link; }   //从pa链中摘下
   else
 { q = pb;  pb = pb->link; }   //从pb链中摘下
   q->link = first->link;  first->link = q;  //链入结果链的链头
} p = ( pa != NULL ) ? pa : pb;    //处理未完链的剩余部分
  while ( p != NULL ) {
  q = p;  p = p->link;
   q->link = first->link;  first->link = q;
}
}

本实验已在BorlandC++3.1中编译通过，下面是编译执行的结果：