反转链表（递归实现）

5970阅读　0评论2015-03-03　qinchaowhut
分类：C/C++

反转链表

  1. #include<stdio.h>

  3. struct ListNode{
  4.     int m_nKey;
  5.     struct ListNode* m_pNext;
  6. };

  8. void ReverseList(struct ListNode** pHead)
  9. {
  10.     struct ListNode *ReverseHead=NULL;
  11.     struct ListNode *pNode=*pHead;
  12.     struct ListNode *pPrev=NULL;
  13.     struct ListNode *pNext=NULL;
  14.     while(pNode!=NULL)
  15.     {
  16.         pNext=pNode->m_pNext;
  17.         if(pNext==NULL)
  18.             *pHead=pNode;
  19.         pNode->m_pNext=pPrev;
  20.         pPrev=pNode;
  21.         pNode=pNext;
  22.     }
  23.     return;
  24. }

  26. void ReverseListX(struct ListNode** pHead,struct ListNode *pNode,struct ListNode *pPrev)
  27. {
  28.     if(pNode!=NULL)
  29.     {
  30.         struct ListNode *pNext=pNode->m_pNext;
  31.         pNode->m_pNext=pPrev;
  32.         pPrev=pNode;
  33.         pNode=pNext;
  34.         ReverseListX(pHead,pNode,pPrev);
  35.     }
  36.     else
  37.         *pHead=pPrev;
  38. }

  40. void CreateList(struct ListNode **pHead)
  41. {
  42.     struct ListNode *tList=NULL;
  43.     int i=0;
  44.     for(;i<10;i++)
  45.     {
  46.         struct ListNode *temp=(struct ListNode *)malloc(sizeof(struct ListNode));
  47.         temp->m_nKey=i;
  48.         temp->m_pNext=NULL;    
  49.         if(tList==NULL)
  50.         {
  51.             tList=temp;
  52.             *pHead=tList;
  53.         }
  54.         else
  55.         {
  56.             tList->m_pNext=temp;
  57.             tList=tList->m_pNext;
  58.         }
  59.     }
  60.     return;
  61. }

  63. void ShowList(struct ListNode *pHead)
  64. {
  65.     struct ListNode *temp=pHead;
  66.     printf("show:\n");
  67.     while(temp!=NULL)
  68.     {
  69.         printf("%d ",temp->m_nKey);
  70.         temp=temp->m_pNext;
  71.     }
  72.     printf("\n");
  73. }

  75. int main()
  76. {
  77.     struct ListNode *pHead=NULL;
  78.     CreateList(&pHead);
  79.     ShowList(pHead);
  80. /*    ReverseList(&pHead);
  81.     ShowList(pHead);*/
  82.     ReverseListX(&pHead,pHead,NULL);
  83.     ShowList(pHead);
  84. //堆上分配内存的释放此处省略；
  85. }


上一篇：C++对象作为函数参数
下一篇：Pow(x, n)