反轉鏈表，反轉

反轉鏈表，反轉

題目：定義一個函數，輸入一個鏈表的頭結點，反轉該鏈表並輸出反轉後鏈表的頭結點。

思路1:定義三個指針，分別指向當前遍歷到的結點、它的前一個結點及後一個結點。

思路2:遞歸

  1 #include<stdio.h> 
  2 #include<tchar.h>
  3 #include<iostream>
  4 struct ListNode
  5 {
  6     int m_nValue;
  7     ListNode* m_pNext;
  8 };
  9 
 10 ListNode* CreateListNode(int value)
 11 {
 12     ListNode* pNode = new ListNode();
 13     pNode->m_nValue = value;
 14     pNode->m_pNext = NULL;
 15     
 16     return pNode;    
 17 }
 18 
 19 void PrintList(ListNode* pHead)
 20 {
 21     printf("PrintList starts.\n");
 22     ListNode* pNode = pHead;
 23     while(pNode != NULL)
 24     {
 25         printf("%d\t",pNode->m_nValue);
 26         pNode = pNode->m_pNext;
 27     }
 28     printf("\nPrintList ends.\n");
 29 }
 30 
 31 void DestoryList(ListNode* pHead)
 32 {
 33     ListNode* pNode = pHead;
 34     while(pNode != NULL)
 35     {
 36         pHead = pHead->m_pNext;
 37         delete pNode;
 38         pNode = pHead;
 39     }
 40 }
 41 
 42 void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
 43 {
 44     if(pCurrent == NULL)
 45     {
 46         printf("Error to connect two nodes.\n");
 47         exit(1);
 48     }
 49     
 50     pCurrent->m_pNext = pNext;
 51 }
 52 
 53 
 54 //循環， 定義三個指針 
 55 ListNode* ReverseList1(ListNode* pHead)
 56 {
 57     ListNode* pReversedHead = NULL;
 58     ListNode* pNode = pHead;
 59     ListNode* pPrev = NULL;
 60     while(pNode != NULL)
 61     {
 62         ListNode* pNext = pNode->m_pNext;
 63         
 64         if(pNext == NULL)
 65             pReversedHead = pNode;
 66         
 67         pNode->m_pNext = pPrev;
 68         
 69         pPrev = pNode;
 70         pNode = pNext;
 71     }
 72     
 73     return pReversedHead;
 74 }
 75 
 76 
 77 //遞歸 將當前結點的下一個結點保存好， 並將當前結點從鏈表中取出，再遞歸處理以後的鏈表 
 78 ListNode* ReverseList2(ListNode* pPrev)
 79 {
 80     if(pPrev->m_pNext == NULL)
 81         return pPrev;
 82 
 83     ListNode* pNext = pPrev->m_pNext;
 84     pPrev->m_pNext = NULL;
 85     ListNode* pReversedHead = ReverseList2(pNext);
 86     pNext->m_pNext = pPrev;
 87     return pReversedHead;
 88 }
 89 
 90 int main()
 91 {
 92     ListNode* pNode1 = CreateListNode(1);
 93     ListNode* pNode2 = CreateListNode(2);
 94     ListNode* pNode3 = CreateListNode(3);
 95     ListNode* pNode4 = CreateListNode(4);
 96     ListNode* pNode5 = CreateListNode(5);
 97     
 98     ConnectListNodes(pNode1, pNode2);
 99     ConnectListNodes(pNode2, pNode3);
100     ConnectListNodes(pNode3, pNode4);
101     ConnectListNodes(pNode4, pNode5);
102     
103     printf("Sloution1:\n");
104     printf("The original list is: \n");
105     PrintList(pNode1);
106     
107     ListNode* pReversedHead = ReverseList1(pNode1);
108     
109     printf("The reversed list is: \n");
110     PrintList(pReversedHead);
111     
112     printf("\n");
113     
114     printf("Sloution2:\n");
115     printf("The original list is: \n");
116     PrintList(pReversedHead);
117     
118     pReversedHead = ReverseList2(pReversedHead);
119     
120     printf("The reversed list is: \n");
121     PrintList(pReversedHead);
122         
123     DestoryList(pReversedHead);
124     
125     return 0;
126 }