不用辅助节点，实现单链表的反转。

http://bbs.chinaunix.net/forum/23/20041101/436188.html

 GAORJ 的问题如下：

 有一单链表n1->n2->...n(x-1)->nx,请问如何在不使用辅助节点的情况下实现该链表的反转呢? 反转后变成nx->n(x-1)->...n2->n1 .

 （随机测试，最大最至20000，都能有正确的结果）

代码如下：

#include <stdio.h>
#include <stdlib.h>

#define SWAP(a,b) { \
 a=a^0xFFFFFFFF; \
 b=b^a; \
 a=a^b; \
 b=b^0xFFFFFFFF; \
 b=b^a; \
 }
#define SWAP_POINT(pA,pB) {\
 int h,t; \
 pLinkList ph,pt; \
 h=(int)pA; \
 t=(int)pB; \
 ph = (pLinkList)h; \
 pt = (pLinkList)t; \
 SWAP(h,t); \
 pA = (pLinkList)h; \
 pB = (pLinkList)t; \
 }

typedef struct tagLinkList
{
 int data;
 struct tagLinkList *next;
} LinkList , *pLinkList ;

int main(int argc, char* argv[])
{
 int count,i;
 pLinkList Head,tmpNode,Tail;
 
 Head=NULL;
 
 // Construct LinkList.
 printf("Enter count:"); scanf("%d",&count);
 if(count <= 1)
 {
  printf("Count error,must large than 1.\n");
  exit(1);
 }
 for(i=1;i<=count;++i)
 {
  tmpNode=(LinkList *)malloc(sizeof(LinkList));
  tmpNode->data=i;
  printf("No.=%d\t Address:%X , Data:%d\n",i,tmpNode,tmpNode->data);
  if(!Head)
   Tail=Head=tmpNode;
  
  else{
   Tail->next=tmpNode;
   Tail=tmpNode;
  }
 }
 Tail->next=NULL;
 
 // Reverse LinkList.
 if(2 == count) {
  //N=2
  SWAP_POINT(Head,Tail->next);
  SWAP_POINT(Head,Tail);
  SWAP_POINT(Head->next->next,Tail);
 }else if(3 == count) {
  //N=3
  SWAP_POINT(Head->next,Tail->next);
  SWAP_POINT(Head,Tail);
  SWAP_POINT(Head->next->next,Tail);
 }else{
  //N>=4
  SWAP_POINT(Head->next,Tail->next);
  SWAP_POINT(Head,Tail);
  SWAP_POINT(Head->next->next,Tail);
  SWAP_POINT(Head->next,Tail->next);
  SWAP_POINT(Head->next->next,Tail);
  for(i=6;i<=count;++i)
  {
   SWAP_POINT(Head->next,Tail);
   SWAP_POINT(Head->next->next,Tail);
  }
 }
 
 //Output reversed LinkList.
 tmpNode=Head;
 printf("After reverse.\n");
 for(i=1;i<=count;++i)
 {
  printf("No.=%d\t Address:%X , Data:%d\n",i,tmpNode,tmpNode->data);
  tmpNode = tmpNode->next;
 }
 
 //Release LinkList
 printf("Release LinkList.\n");
 for(i=1;i<=count;++i)
 {
  tmpNode=Head;
  Head = Head->next;
  free(tmpNode);
 }

 return 0;
}

本文地址：http://com.8s8s.com/it/it25797.htm