首页 > 代码库 > (转)单链表的逆置

(转)单链表的逆置

2024-07-10 14:43:50   224人阅读

 

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

（1）利用辅助指针

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

         实现代码：

 1 typedef int DataType; //类型定义 2 typedef struct node{  //单链表定义 3       DataType data; 4       struct node* next; 5 }LinkedNode,*LinkList; 6 void ReverseList(LinkList& ListHead) 7 { 8     cout<<"Begin to Reverse the List"<<endl; 9     if( (NULL==ListHead)||(NULL==ListHead->next) )return ;  //边界检测10     LinkedNode* pPre=ListHead;    //先前指针11     LinkedNode* pCur=pPre->next;  //当前指针12     LinkedNode* pNext=NULL;       //后继指针13     while(pCur!=NULL)14     {15         pNext=pCur->next;16         pCur->next=pPre;17         pPre=pCur;18         pCur=pNext;19     }20     ListHead->next=NULL;21     ListHead=pPre;        //记录下新的头结点22 }

 示意图：

 

（2）递归

         基本思想：在对当前结点逆置时，先递归地逆置其后继结点，然后将后继结点指向当前结点。

         实现代码

　　　写了两个版本

　　　I 返回值为空

        

 1 void ReverseList(LinkedNode* pCur,LinkList& ListHead) 2 { 3     if( (NULL==pCur)||(NULL==pCur->next) ) 4     { 5         ListHead=pCur; 6     } 7     else 8     { 9         LinkedNode* pNext=pCur->next;10         ReverseList(pNext,ListHead); //递归逆置后继结点11         pNext->next=pCur;            //将后继结点指向当前结点。12         pCur->next=NULL;13     }14 }

II、返回值为结点类型

 

 1 LinkedNode* ReverseList(LinkedNode* pCur,LinkList& ListHead) 2 { 3     cout<<"Begin to Reverse the List"<<endl; 4     if( (NULL==pCur)||(NULL==pCur->next) ) 5     { 6             ListHead=pCur; 7             return pCur; 8     } 9     else10     {11         LinkedNode* pTemp=ReverseList(pCur->next,ListHead); //递归逆置后继结点12         pTemp->next=pCur;   //将后继结点指向当前结点13         pCur->next=NULL;14         return pCur;15     }16 }

示意图：

        

下面给出完整的程序：

 1 #include<iostream> 2 using namespace std; 3 const int N=6; 4 typedef int DataType;//类型定义 5 typedef struct node{ //单链表 6       DataType data; 7       struct node* next; 8 }LinkedNode,*LinkList; 9 /****由数组创建单链表****/10 LinkList CreateList(DataType a[N])11 {12     LinkedNode* ListHead=new LinkedNode();13     ListHead->data=http://www.mamicode.com/a[0];14     ListHead->next=NULL;15     for(int i=N-1;i>=1;i--)16     {17         LinkedNode* p=new LinkedNode();18         p->data=http://www.mamicode.com/a[i];19         p->next=ListHead->next;20         ListHead->next=p;21     }22     return ListHead;23 }24 /****输出单链表****/25 void PrintList(LinkList ListHead)26 {27     if(NULL==ListHead)cout<<"The List is empty!"<<endl;28     else29     {30         LinkedNode* p=ListHead;31         while(p!=NULL)32         {33             cout<<p->data<<" ";34             p=p->next;35         }36         cout<<endl;37     }38 }39 void ReverseList(LinkedNode* pCur,LinkList& ListHead)40 {41     if( (NULL==pCur)||(NULL==pCur->next) )42     {43         ListHead=pCur;44     }45     else46     {47         LinkedNode* pNext=pCur->next;48         ReverseList(pNext,ListHead); //递归逆置后继结点49         pNext->next=pCur;            //将后继结点指向当前结点。50         pCur->next=NULL;51     }52 }53 int main()54 {55     int a[N]={1,2,3,4,5,6}; 56     LinkedNode* list=CreateList(a);57     PrintList(list);58     LinkedNode*pTemp=list;59     ReverseList(pTemp,list);60     PrintList(list);61     return 0;62 }

 


联系
我们