单链表倒置思想

前端之家收集整理的这篇文章主要介绍了单链表倒置思想前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

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

(1)利用辅助指针

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

实现代码

  1. typedefintDataType;//类型定义
  2. typedefstructnode{//单链表定义
  3. DataTypedata;
  4. structnode*next;
  5. }LinkedNode,*LinkList;
  6. voidReverseList(LinkList&ListHead)
  7. {
  8. cout<<"BegintoReversetheList"<<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. voidReverseList(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<<"BegintoReversetheList"<<endl;
  4. if((NULL==pCur)||(NULL==pCur->next))
  5. {
  6. ListHead=pCur;
  7. returnpCur;
  8. }
  9. else
  10. {
  11. LinkedNode*pTemp=ReverseList(pCur->next,ListHead);//递归逆置后继结点
  12. pTemp->next=pCur;//将后继结点指向当前结点
  13. pCur->next=NULL;
  14. returnpCur;
  15. }
  16. }



示意图:

下面给出完整的程序:

  1. #include<iostream>
  2. usingnamespacestd;
  3. constintN=6;
  4. typedefintDataType;//类型定义
  5. typedefstructnode{//单链表
  6. DataTypedata;
  7. structnode*next;
  8. }LinkedNode,*LinkList;
  9. /****由数组创建单链表****/
  10. LinkListCreateList(DataTypea[N])
  11. {
  12. LinkedNode*ListHead=newLinkedNode();
  13. ListHead->data=a[0];
  14. ListHead->next=NULL;
  15. for(inti=N-1;i>=1;i--)
  16. {
  17. LinkedNode*p=newLinkedNode();
  18. p->data=a[i];
  19. p->next=ListHead->next;
  20. ListHead->next=p;
  21. }
  22. returnListHead;
  23. }
  24. /****输出单链表****/
  25. voidPrintList(LinkListListHead)
  26. {
  27. if(NULL==ListHead)cout<<"TheListisempty!"<<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. voidReverseList(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. intmain()
  54. {
  55. inta[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. return0;
  62. }
原文链接:https://www.f2er.com/javaschema/286577.html

猜你在找的设计模式相关文章