// Rlink.cpp : Defines the entry point for the console application.
//
// 作者：辛占福
// 日期：2009-9-21
// 内容：链表逆序
#include "stdafx.h"
typedef struct LNode
{
char c;
struct LNode *Next;
}LNode,*pNode;
pNode RevList_2(pNode phead)
{
pNode pbegin = phead;
pNode pDel = phead;
pNode pEnd = phead;
pNode pIteration = phead;
int IIteration = 0;
if (phead == NULL || phead->Next == NULL)
return phead;
// 找到逆序前链表的尾端
while (pIteration != NULL)
{
pEnd = pIteration;
// 记录链表的结点数
IIteration++;
pIteration = pIteration->Next;
}
int iCount = 0;
/* 正序：a->b->c->d->e
* 思想：采用尾插法，即：从链表头取节点插入到逆序前的链表尾端节点前。
* 算法：1、b->c->d->e->a
* 2、c->d->e->b->a
* 3、d->e->c->b->a
* 4、e->d->c->b->a --逆序完成
*/
while (iCount < (IIteration - 1))
{
pbegin = pDel->Next;
if (iCount == 0)
pDel->Next = NULL;
else
pDel->Next = pEnd->Next;
pEnd->Next = pDel;
pDel = pbegin;
iCount++;
}
return phead=pbegin;
}
pNode RevList(pNode phead)
{
pNode p, q, r;
if (phead == NULL || phead->Next == NULL)
return phead;
p = phead->Next;
q = p->Next;
r = q->Next;
p->Next = NULL;
while (r != NULL)
{
q->Next = p;
p = q;
q = r;
r = r->Next;
}
q->Next = p;
phead->Next = q;
return phead;
}
void Print_N(pNode h)
{
pNode pHead = h;
if (h == NULL)
return;
while(pHead != NULL)
{
printf("%c ", pHead->c);
pHead = pHead->Next;
}
printf("\n");
}
int main(int argc, char* argv[])
{
LNode n1;
LNode n2;
LNode n3;
LNode n4;
LNode n5;
n1.c = 'a';
n1.Next = &n2;
n2.c = 'b';
n2.Next = &n3;
n3.c = 'c';
n3.Next = &n4;
n4.c = 'd';
n4.Next = &n5;
n5.c = 'e';
n5.Next = NULL;
Print_N(&n1);
printf("RevList: \n");
Print_N(RevList_2(&n1));
return 0;
}
