(1)利用辅助指针
在遍历结点过程中,设置辅助指针,用于记录先前遍历的结点。这样依次编译的过程中只需修改其后继结点的next域即可
-
typedef int DataType; //类型定义
-
typedef struct node{ //单链表定义
-
DataType data;
-
struct node* next;
-
}LinkedNode,*LinkList;
-
void ReverseList(LinkList& ListHead)
-
{
-
cout<<"Begin to Reverse the List"<<endl;
-
if( (NULL==ListHead)||(NULL==ListHead->next) )return ; //边界检测
-
LinkedNode* pPre=ListHead; //先前指针
-
LinkedNode* pCur=pPre->next; //当前指针
-
LinkedNode* pNext=NULL; //后继指针
-
while(pCur!=NULL)
-
{
-
pNext=pCur->next;
-
pCur->next=pPre;
-
pPre=pCur;
-
pCur=pNext;
-
}
-
ListHead->next=NULL;
-
ListHead=pPre; //记录下新的头结点
-
}
(2)递归
在对当前结点逆置时,先递归地逆置其后继结点,然后将后继结点指向当前结点。
两个版本
I、返回值为空
-
void ReverseList(LinkedNode* pCur,LinkList& ListHead)
-
{
-
if( (NULL==pCur)||(NULL==pCur->next) )
-
{
-
ListHead=pCur;
-
}
-
else
-
{
-
LinkedNode* pNext=pCur->next;
-
ReverseList(pNext,ListHead); //递归逆置后继结点
-
pNext->next=pCur; //将后继结点指向当前结点。
-
pCur->next=NULL;
-
}
-
}
II、返回值为结点类型
-
LinkedNode* ReverseList(LinkedNode* pCur,LinkList& ListHead)
-
{
-
cout<<"Begin to Reverse the List"<<endl;
-
if( (NULL==pCur)||(NULL==pCur->next) )
-
{
-
ListHead=pCur;
-
return pCur;
-
}
-
else
-
{
-
LinkedNode* pTemp=ReverseList(pCur->next,ListHead); //递归逆置后继结点
-
pTemp->next=pCur; //将后继结点指向当前结点
-
pCur->next=NULL;
-
return pCur;
-
}
-
}
阅读(948) | 评论(0) | 转发(0) |