//链表的一些操作，类实现：包括链表建立、逆向输出（递归，时间复杂O(N)）、就地转置（递归，最坏时间复杂O（N））

Link.h：定义了类及基本操作

#include <iostream>

using namespace std;
typedef int Elem;
struct LNode
{
 Elem data;
 LNode *next;
};
struct LinkStruct
{
 LNode *head;
 LNode *tail;
 int len;
};

class Link
{
public:
 Link();
 ~Link(){};
 Traverse();
 RevTraverse();
 GetLen();
 LNode *PHead();
 Elem MidValue(Link L);
 Rev();
private:
 LinkStruct L;
 void Create();
 revout(LNode *p);
 out();
 LNode *Rev(LNode *p);
};

Link::Link()
{
 Create();
}

void Link::Create()
{
 cout<<"请输入各个结点，0为退出"<<endl;
 Elem data;
 LNode *p;
 L.len=0;
 p=L.head=new LNode;
 
 while(cin>>data)
 {
  if(data==0)
  {
   p->next=NULL;
   break;
  }
  else
  {
    p->next=new LNode;
    p=p->next;
    L.len++;
    p->data=data;
  }
 }
}

Link::out()
{
 LNode *p=L.head->next;
 while(p!=NULL)
 {
  cout<<p->data<<endl;
  p=p->next;
 }
}

Link::revout(LNode *p)
{
 if(p->next==NULL)
 {
  cout<<p->data<<endl;
 }
 else
 {
  revout(p->next);
  cout<<p->data<<endl;
 }
}

Link::RevTraverse()
{
 cout<<"开始反向输出："<<endl;
 revout(L.head->next);
}

Link::Traverse()
{
 cout<<"开始正向输出："<<endl;
 out();
}

Link::GetLen()
{
 return L.len;
}
LNode * Link::PHead()
{
 return this->L.head->next;
}

Link::MidValue(Link L)
{
 LNode *p1=L.PHead();
 LNode *p2=this->L.head->next;
 int mid=(L.GetLen()+this->L.len)/2,i=0;
 Elem value;
 while(i<=mid && p1 && p2)
 {
  if(p1&&p2&&p1->data<=p2->data)
  {
   value=p1->data;
   p1=p1->next;
   i++;
  }
  if(p1&&p2&&p1->data>=p2->data)
  {
   value=p2->data;
   p2=p2->next;
   i++;
  }
 }
 while(i<=mid && p1)
 {
  value=p1->data;
  p1=p1->next;
  i++;
 }
 while(i<=mid && p2)
 {
  value=p2->data;
  p2=p2->next;
  i++;
 }
 return value;
}

Link::Rev()
{
 LNode *p=L.head->next;
 Rev(L.head->next);
 p->next=NULL;
}

LNode *Link::Rev(LNode *p)
{
 if(p->next==NULL)
 {
  L.head->next=p;
  return p;
 }
 else
 {
  Rev(p->next)->next=p;
  return p;
 }
}
main.cpp：主程序

#include "Link.h"

int main()
{
 Link L1;
 L1.Traverse();
 L1.Rev();
 L1.Traverse();
 L1.RevTraverse();
 cout<<L1.GetLen()<<endl;
 cout<<"L1与L2的中值为:"<<L2.MidValue(L1)<<endl;
 return 0;
}