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

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

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;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航