Chinaunix首页 | 论坛 | 博客
  • 博客访问: 290208
  • 博文数量: 95
  • 博客积分: 618
  • 博客等级: 中士
  • 技术积分: 455
  • 用 户 组: 普通用户
  • 注册时间: 2011-03-28 13:39
文章分类

全部博文(95)

文章存档

2015年(65)

2013年(1)

2012年(10)

2011年(19)

分类: C/C++

2015-04-06 17:53:01

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



阅读(951) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~