如何把一個單鏈表進行反轉？
方法1：將單鏈表儲存為數組，然后按照數組的索引逆序進行反轉。
方法2：使用3個指針遍歷單鏈表，逐個鏈接點進行反轉。
方法3：從第2個節點到第N個節點，依次逐節點插入到第1個節點(head節點)之后，最后將第一個節點挪到新表的表尾。
方法4: 遞歸(相信我們都熟悉的一點是，對于樹的大部分問題，基本可以考慮用遞歸來解決。但是我們不太熟悉的一點是，對于單鏈表的一些問題，也可以使用遞歸?？梢哉J為單鏈表是一顆永遠只有左(右)子樹的樹，因此可以考慮用遞歸來解決?；蛘哒f，因為單鏈表本身的結構也有自相似的特點，所以可以考慮用遞歸來解決)
方法1：
浪費空間。
方法2:
使用p和q兩個指針配合工作，使得兩個節點間的指向反向，同時用r記錄剩下的鏈表。
p = head;
q = head->next;
head->next = NULL;
現在進入循環體，這是第一次循環。
r = q->next;
q->next = p;
p = q;
q =r;
第二次循環。
r = q->next
q->next = p;
p = q;
q = r
第三次循環。。。。。
具體代碼如下
ActList* ReverseList2(ActList* head){ //ActList* temp=new ActList; if(NULL==head|| NULL==head->next) return head; //少于兩個節點沒有反轉的必要。 ActList* p; ActList* q; ActList* r; p = head; q = head->next; head->next = NULL; //舊的頭指針是新的尾指針，next需要指向NULL while(q){ r = q->next; //先保留下一個step要處理的指針 q->next = p; //然后p q交替工作進行反向 p = q; q = r; } head=p; // 最后q必然指向NULL，所以返回了p作為新的頭指針 return head; }updated 2014-01-24，重新非IDE環境寫了一遍
如果覺得上面的先成環再斷環的過程不太好理解，那么可以考慮下面這個辦法，增加一個中間變量，使用三個變量來實現。
struct ListNode{ int val; ListNode* next; ListNode(int a):val(a),next(NULL){}};ListNode* reverseLinkedList3(ListNode* head){ if(head==NULL||head->next==NULL) return head; ListNode* p=head; //指向head ListNode* r=head->next; //指向待搬運的節點，即依次指向從第2個節點到最后一個節點的所有節點 ListNode* m=NULL; //充當搬運工作用的節點 ListNode* tail=head->next; while(r!=NULL){ //bug2 循環語句寫錯了, while寫成了if m=r; r=r->next; m->next=p->next; p->next=m; //if(r!=NULL) //std::cout<<"m="<<m->val<<" ,p="<<p->val<<" ,r="<<r->val<<std::endl; //else //std::cout<<"m="<<m->val<<" ,p="<<p->val<<" ,r=NULL"<<std::endl; } head=p->next; tail->next=p; p->next=NULL; tail=p; return head; // bug1 忘記了return }方法3
還是先看圖，
從圖上觀察，方法是：對于一條鏈表，從第2個節點到第N個節點，依次逐節點插入到第1個節點(head節點)之后，(N-1)次這樣的操作結束之后將第1個節點挪到新表的表尾即可。
代碼如下:
ActList* ReverseList3(ActList* head){ ActList* p; ActList* q; p=head->next; while(p->next!=NULL){ q=p->next; p->next=q->next; q->next=head->next; head->next=q; } p->next=head;//相當于成環 head=p->next->next;//新head變為原head的next p->next->next=NULL;//斷掉環 return head; }附:
完整的鏈表創建，顯示，反轉代碼:
//創建:用q指向當前鏈表的最后一個節點；用p指向即將插入的新節點。//反向:用p和q反轉工作，r記錄鏈表中剩下的還未反轉的部分。#include "stdafx.h"#include <iostream>using namespace std;struct ActList{ char ActName[20]; char Director[20]; int Mtime; ActList *next;};ActList* head;ActList* Create(){//start of CREATE() ActList* p=NULL; ActList* q=NULL; head=NULL; int Time; cout<<"Please input the length of the movie."<<endl; cin>>Time; while(Time!=0){ p=new ActList; //類似表達: TreeNode* node = new TreeNode;//Noice that [new] should be written out. p->Mtime=Time; cout<<"Please input the name of the movie."<<endl; cin>>p->ActName; cout<<"Please input the Director of the movie."<<endl; cin>>p->Director; if(head==NULL) { head=p; } else { q->next=p; } q=p; cout<<"Please input the length of the movie."<<endl; cin>>Time; } if(head!=NULL) q->next=NULL; return head;}//end of CREATE()void DisplayList(ActList* head){//start of display cout<<"show the list of programs."<<endl; while(head!=NULL) { cout<<head->Mtime<<"/t"<<head->ActName<<"/t"<<head->Director<<"/t"<<endl; head=head->next; }}//end of displayActList* ReverseList2(ActList* head){ //ActList* temp=new ActList; if(NULL==head|| NULL==head->next) return head; ActList* p; ActList* q; ActList* r; p = head; q = head->next; head->next = NULL; while(q){ r = q->next; // q->next = p; p = q; // q = r; // } head=p; return head; }ActList* ReverseList3(ActList* head){ ActList* p; ActList* q; p=head->next; while(p->next!=NULL){ q=p->next; p->next=q->next; q->next=head->next; head->next=q; } p->next=head;//相當于成環 head=p->next->next;//新head變為原head的next p->next->next=NULL;//斷掉環 return head; }int main(int argc, char* argv[]){// DisplayList(Create());// DisplayList(ReverseList2(Create())); DisplayList(ReverseList3(Create())); return 0;}方法4: 遞歸
updated: 2014-01-24
因為發現大部分問題都可以從遞歸角度想想，所以這道題目也從遞歸角度想了想。
現在需要把A->B->C->D進行反轉，
可以先假設B->C->D已經反轉好，已經成為了D->C->B,那么接下來要做的事情就是將D->C->B看成一個整體，讓這個整體的next指向A，所以問題轉化了反轉B->C->D。那么，
可以先假設C->D已經反轉好，已經成為了D->C,那么接下來要做的事情就是將D->C看成一個整體，讓這個整體的next指向B，所以問題轉化了反轉C->D。那么，
可以先假設D(其實是D->NULL)已經反轉好，已經成為了D(其實是head->D),那么接下來要做的事情就是將D(其實是head->D)看成一個整體，讓這個整體的next指向C，所以問題轉化了反轉D。
上面這個過程就是遞歸的過程，這其中最麻煩的問題是，如果保留新鏈表的head指針呢？想到了兩個辦法。
// 遞歸版的第一種實現，借助類的成員變量m_phead來表示新鏈表的頭指針。struct ListNode{ int val; ListNode* next; ListNode(int a):val(a),next(NULL){}};class Solution{ ListNode* reverseLinkedList4(ListNode* head){ //輸入: 舊鏈表的頭指針 if(head==NULL) return NULL; if(head->next==NULL){ m_phead=head; return head; } ListNode* new_tail=reverseLinkedList4(head->next); new_tail->next=head; head->next=NULL; return head; //輸出: 新鏈表的尾指針 } ListNode* m_phead=NULL;//member variable defined for reverseLinkedList4(ListNode* head)};第二個辦法是，增加一個引用型參數 new_head，它用來保存新鏈表的頭指針。
struct ListNode{ int val; ListNode* next; ListNode(int a):val(a),next(NULL){}};class Solution{ ListNode* reverseLinkedList5(ListNode* head, ListNode* & new_head){ //輸入參數head為舊鏈表的頭指針。new_head為新鏈表的頭指針。 if(head==NULL) return NULL; if(head->next==NULL){ new_head=head; //當處理到了舊鏈表的尾指針，也就是新鏈表的頭指針時，對new_head進行賦值。因為是引用型參數，所以在接下來調用中new_head的值逐層傳遞下去。 return head; } ListNode* new_tail=reverseLinkedList5(head->next,new_head); new_tail->next=head; head->next=NULL; return head; //輸出參數head為新鏈表的尾指針。 }};總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對武林網的支持。
新聞熱點
疑難解答
圖片精選
