沈阳网站建设开发维护,北京个人网站设计,用网站做简历,杭州最专业的seo公司转自#xff1a;http://blog.csdn.net/heyabo/article/details/7610732 对于单链表的逆置有两种方法可以实现#xff1a; #xff08;1#xff09;利用辅助指针 基本思想#xff1a;在遍历结点过程中#xff0c;设置辅助指针#xff0c;用于记录先前遍历的结点。这样依次… 转自http://blog.csdn.net/heyabo/article/details/7610732 对于单链表的逆置有两种方法可以实现 1利用辅助指针 基本思想在遍历结点过程中设置辅助指针用于记录先前遍历的结点。这样依次编译的过程中只需修改其后继结点的next域即可。 实现代码 [cpp] view plaincopy print? typedef int DataType; //类型定义 typedef struct node{ //单链表定义 DataType data; struct node* next; }LinkedNode,*LinkList; void ReverseList(LinkList ListHead) { coutBegin to Reverse the Listendl; if( (NULLListHead)||(NULLListHead-next) )return ; //边界检测 LinkedNode* pPreListHead; //先前指针 LinkedNode* pCurpPre-next; //当前指针 LinkedNode* pNextNULL; //后继指针 while(pCur!NULL) { pNextpCur-next; pCur-nextpPre; pPrepCur; pCurpNext; } ListHead-nextNULL; ListHeadpPre; //记录下新的头结点 } 示意图 2递归 基本思想在对当前结点逆置时先递归地逆置其后继结点然后将后继结点指向当前结点。 实现代码 写了两个版本 I、返回值为空 [cpp] view plaincopy print? void ReverseList(LinkedNode* pCur,LinkList ListHead) { if( (NULLpCur)||(NULLpCur-next) ) { ListHeadpCur; } else { LinkedNode* pNextpCur-next; ReverseList(pNext,ListHead); //递归逆置后继结点 pNext-nextpCur; //将后继结点指向当前结点。 pCur-nextNULL; } } II、返回值为结点类型 [cpp] view plaincopy print? LinkedNode* ReverseList(LinkedNode* pCur,LinkList ListHead) { coutBegin to Reverse the Listendl; if( (NULLpCur)||(NULLpCur-next) ) { ListHeadpCur; return pCur; } else { LinkedNode* pTempReverseList(pCur-next,ListHead); //递归逆置后继结点 pTemp-nextpCur; //将后继结点指向当前结点 pCur-nextNULL; return pCur; } } 示意图 下面给出完整的程序 [cpp] view plaincopy print? #includeiostream using namespace std; const int N6; typedef int DataType;//类型定义 typedef struct node{ //单链表 DataType data; struct node* next; }LinkedNode,*LinkList; /****由数组创建单链表****/ LinkList CreateList(DataType a[N]) { LinkedNode* ListHeadnew LinkedNode(); ListHead-dataa[0]; ListHead-nextNULL; for(int iN-1;i1;i--) { LinkedNode* pnew LinkedNode(); p-dataa[i]; p-nextListHead-next; ListHead-nextp; } return ListHead; } /****输出单链表****/ void PrintList(LinkList ListHead) { if(NULLListHead)coutThe List is empty!endl; else { LinkedNode* pListHead; while(p!NULL) { coutp-data ; pp-next; } coutendl; } } void ReverseList(LinkedNode* pCur,LinkList ListHead) { if( (NULLpCur)||(NULLpCur-next) ) { ListHeadpCur; } else { LinkedNode* pNextpCur-next; ReverseList(pNext,ListHead); //递归逆置后继结点 pNext-nextpCur; //将后继结点指向当前结点。 pCur-nextNULL; } } int main() { int a[N]{1,2,3,4,5,6}; LinkedNode* listCreateList(a); PrintList(list); LinkedNode*pTemplist; ReverseList(pTemp,list); PrintList(list); return 0; }
