单链表的逆置-C++实现(五十四)

本文主要是介绍单链表的逆置-C++实现(五十四)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对于单链表的逆置有两种方法可以实现：

（1）利用辅助指针

基本思想：在遍历结点过程中，设置辅助指针，用于记录先前遍历的结点。这样依次编译的过程中只需修改其后继结点的next域即可。

实现代码：

[cpp] view plain copy

print ?

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、返回值为空

[cpp] view plain copy
print ?

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、返回值为结点类型

[cpp] view plain copy
print ?

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;
    }
}