大家老讨论一下,看看这个算法如何实现啊,如果用双链表的话,比较好实现,但是现在是要求单链表来实现,大家来讨论一下,看看用单链表如何来实现这个算法啊?

template <class KeyType, class DataType>
class SLNode
{
public:
 KeyType key;
 DataType data;
 SLNode<KeyType,DataType> *next;
};

template <class KeyType, class DataType>
SLNode<KeyType,DataType> *QuickSort(SLNode<KeyType,DataType> *first)
{
 KeyType firstKey;
 SLNode<KeyType,DataType> *small_first, *small_last, *big_first, *big_last, *cur;
 if(first==NULL)
  return NULL;
 else
 {
  small_first=NULL;
  big_first=NULL;
  small_last=NULL;
  big_last=NULL;
  firstKey=first->key;
  for(cur=first->next;cur!=NULL;cur=cur->next)
  {
   if(cur->key<firstKey)
   {
    if(small_first==NULL)
    {
     small_first=cur;
     small_last=cur;
    }
    else
    {
     small_last->next=cur;
     small_last=cur;
    }
   }
   else
   {
    if(big_first==NULL)
    {
     big_first=cur;
     big_last=cur;
    }
    else
    {
     big_last->next=cur;
     big_last=cur;
    }

   }
  }
  if(small_last!=NULL)
   small_last->next=NULL;
  if(big_last!=NULL)
   big_last->next=NULL;
  small_first = QuickSort(small_first);
  big_first = QuickSort(big_first);
  first->next=big_first;
  if(small_first!=NULL)
  {
   for(cur=small_first;cur->next!=NULL;cur=cur->next);
   cur->next=first;
   first=small_first;
  }
  return first;
 }
}

void main()
{
 int i;
 SLNode<int,int> *first, *last, *p;
 srand((unsigned)time( NULL ));
 first=NULL;
 for(i=1;i<=100;i++)
 {
  p=new SLNode<int,int>;
  p->data=i;
  p->key=rand();
  if(first==NULL)
  {
   first=p;
   last=p;
  }
  else
  {
   last->next=p;
   last=p;
  }
 }
 last->next=NULL;
 for(p=first;p!=NULL;p=p->next)
  cout<<p->key<<","<<p->data<<"; ";
 cout<<endl<<endl;
 first = QuickSort(first);
 for(p=first;p!=NULL;p=p->next)
  cout<<p->key<<","<<p->data<<"; ";
 cout<<endl;
}