单链表的逆置-C++实现

快来打我* 2022-08-20 13:07 172阅读 0赞

原文：http://blog.csdn.net/heyabo/article/details/7610732

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

（1）利用辅助指针

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

实现代码：

**\[cpp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

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. \}

示意图：

> > ![1338215225_3641.jpg][]

（2）递归

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

实现代码：

> > 写了两个版本
> 
> > I、返回值为空
> > 
> > **\[cpp\]** [view plain][] [copy][view plain]
> > 
> > [print][view plain] [?][view plain]
> > 
> > 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、返回值为结点类型
> > 
> > **\[cpp\]** [view plain][] [copy][view plain]
> > 
> > [print][view plain] [?][view plain]
> > 
> > 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. \} 
> > 
> >   
> >   
> > 
> 
> >   
> >

示意图：

![1338215635_9206.jpg][]

下面给出完整的程序：

**\[cpp\]** [view plain][] [copy][view plain]

[print][view plain] [?][view plain]

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=a\[0\]; 
14.  ListHead->next=NULL; 
15. **for**(**int** i=N-1;i>=1;i--) 
16.  \{ 
17.  LinkedNode\* p=**new** LinkedNode(); 
18.  p->data=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. **else**
29.  \{ 
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. **else**
46.  \{ 
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. \}

[view plain]: http://blog.csdn.net/heyabo/article/details/7610732#
[1338215225_3641.jpg]: https://img-my.csdn.net/uploads/201205/28/1338215225_3641.jpg
[1338215635_9206.jpg]: https://img-my.csdn.net/uploads/201205/28/1338215635_9206.jpg