寫一個遞歸版本的鏈表轉置程序

鏈表的轉置是一個很常見、很基礎的數據結構題了，非遞歸的算法很簡單，用三個臨時指針在鏈表上循環一遍即可，不再贅述。遞歸算法也是比較簡單的，但是如果思路不清晰估計也難一時半會兒寫出來把。下面是遞歸版本的鏈表轉置程序：

[cpp] 
#include <iostream>  
using namespace std; 
 
typedef struct Node 
{ 
    Node(int v, Node *ptr=NULL) : data(v), next(ptr) {} 
    int data; 
    Node *next; 
}sNode; 
 
//LB_c: 輸出鏈表，head為鏈表頭指針  
void outputList(sNode *head) 
{ 
    sNode *p = head; 
    while (p != NULL) 
    { 
    cout << p->data << " -> "; 
    p = p->next; 
    } 
    cout << "NULL" << endl; 
} 
 
//LB_c: 轉置鏈表的遞歸方法實現  
sNode* reverseList(sNode *head) 
{ 
    //LB_c: 異常判斷(NULL==head)結束條件(NULL==head->nex),  
    // 即head為最後一個節點時，將該節點返回，即為轉置鏈表的頭節點。  
    if ( (NULL == head) || (NULL == head->next) ) 
    return head; 
    //LB_c: 遞歸後續鏈表（即以head->next為首節點的鏈表）  
    sNode *pNewHead = reverseList(head->next); 
    //LB_c: 上一步執行完後，head->next為後續鏈表的末尾節點，  
    //所以讓head->next的next指向當前節點head  
    head->next->next = head; 
    //LB_c: 當前節點的next指向NULL  
    head->next = NULL; 
    //LB_c: 返回後續鏈表的頭指針  
    return pNewHead; 
} 
 
int main() 
{ 
    //LB_c: 創建鏈表  
    sNode n5(5); 
    sNode n4(4, &n5); 
    sNode n3(3, &n4); 
    sNode n2(2, &n3); 
    sNode n1(1, &n2); 
 
    //LB_c: 輸出原始鏈表  
    outputList(&n1); 
 
    //LB_c: 調用轉置函數  
    sNode *pNew = reverseList(&n1); 
 
    //LB_c: 輸出轉置後的鏈表  
    outputList(pNew); 
 
    return 0; 
} 

#include <iostream>
using namespace std;

typedef struct Node
{
    Node(int v, Node *ptr=NULL) : data(v), next(ptr) {}
    int data;
    Node *next;
}sNode;

//LB_c: 輸出鏈表，head為鏈表頭指針
void outputList(sNode *head)
{
    sNode *p = head;
    while (p != NULL)
    {
 cout << p->data << " -> ";
 p = p->next;
    }
    cout << "NULL" << endl;
}

//LB_c: 轉置鏈表的遞歸方法實現
sNode* reverseList(sNode *head)
{
    //LB_c: 異常判斷(NULL==head)結束條件(NULL==head->nex),
    // 即head為最後一個節點時，將該節點返回，即為轉置鏈表的頭節點。
    if ( (NULL == head) || (NULL == head->next) )
 return head;
    //LB_c: 遞歸後續鏈表（即以head->next為首節點的鏈表）
    sNode *pNewHead = reverseList(head->next);
    //LB_c: 上一步執行完後，head->next為後續鏈表的末尾節點，
    //所以讓head->next的next指向當前節點head
    head->next->next = head;
    //LB_c: 當前節點的next指向NULL
    head->next = NULL;
    //LB_c: 返回後續鏈表的頭指針
    return pNewHead;
}

int main()
{
    //LB_c: 創建鏈表
    sNode n5(5);
    sNode n4(4, &n5);
    sNode n3(3, &n4);
    sNode n2(2, &n3);
    sNode n1(1, &n2);

    //LB_c: 輸出原始鏈表
    outputList(&n1);

    //LB_c: 調用轉置函數
    sNode *pNew = reverseList(&n1);

    //LB_c: 輸出轉置後的鏈表
    outputList(pNew);

    return 0;
}