单链表逆置

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

（1）利用辅助指针

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

         实现代码：

[cpp] view plaincopyprint?

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. 10.     LinkedNode* pPre=ListHead;    //先前指针   
11. 11.     LinkedNode* pCur=pPre->next;  //当前指针   
12. 12.     LinkedNode* pNext=NULL;       //后继指针   
13. 13.     while(pCur!=NULL)  
14. 14.     {  
15. 15.         pNext=pCur->next;  
16. 16.         pCur->next=pPre;  
17. 17.         pPre=pCur;  
18. 18.         pCur=pNext;  
19. 19.     }  
20. 20.     ListHead->next=NULL;  
21. 21.     ListHead=pPre;        //记录下新的头结点   

22. }  

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 plaincopyprint?

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. 10.         ReverseList(pNext,ListHead); //递归逆置后继结点   
11. 11.         pNext->next=pCur;            //将后继结点指向当前结点。   
12. 12.         pCur->next=NULL;  
13. 13.     }  

14. }  

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 plaincopyprint?

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.     else  
10. 10.     {  
11. 11.         LinkedNode* pTemp=ReverseList(pCur->next,ListHead); //递归逆置后继结点   
12. 12.         pTemp->next=pCur;   //将后继结点指向当前结点   
13. 13.         pCur->next=NULL;  
14. 14.         return pCur;  
15. 15.     }  

16. }  

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;

  }

}

 

         示意图：

        

下面给出完整的程序：

[cpp] view plaincopyprint?

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. {  

1. 12.     LinkedNode* ListHead=new LinkedNode();  
2. 13.     ListHead->data=a[0];  
3. 14.     ListHead->next=NULL;  
4. 15.     for(int i=N-1;i>=1;i--)  
5. 16.     {  
6. 17.         LinkedNode* p=new LinkedNode();  
7. 18.         p->data=a[i];  
8. 19.         p->next=ListHead->next;  
9. 20.         ListHead->next=p;  
10. 21.     }  
11. 22.     return ListHead;  

23. }  

24. /****输出单链表****/  

25. void PrintList(LinkList ListHead)  

26. {  

1. 27.     if(NULL==ListHead)cout<<"The List is empty!"<<endl;  
2. 28.     else  
3. 29.     {  
4. 30.         LinkedNode* p=ListHead;  
5. 31.         while(p!=NULL)  
6. 32.         {  
7. 33.             cout<<p->data<<" ";  
8. 34.             p=p->next;  
9. 35.         }  
10. 36.         cout<<endl;  
11. 37.     }  

38. }  

39. void ReverseList(LinkedNode* pCur,LinkList& ListHead)  

40. {  

1. 41.     if( (NULL==pCur)||(NULL==pCur->next) )  
2. 42.     {  
3. 43.         ListHead=pCur;  
4. 44.     }  
5. 45.     else  
6. 46.     {  
7. 47.         LinkedNode* pNext=pCur->next;  
8. 48.         ReverseList(pNext,ListHead); //递归逆置后继结点   
9. 49.         pNext->next=pCur;            //将后继结点指向当前结点。   
10. 50.         pCur->next=NULL;  
11. 51.     }  

52. }  

53. int main()  

54. {  

1. 55.     int a[N]={1,2,3,4,5,6};   
2. 56.     LinkedNode* list=CreateList(a);  
3. 57.     PrintList(list);  
4. 58.     LinkedNode*pTemp=list;  
5. 59.     ReverseList(pTemp,list);  
6. 60.     PrintList(list);  
7. 61.     return 0;  

62. }