如何把一個單鏈表進行反轉？
方法1：將單鏈表儲存為數組，然後按照數組的索引逆序進行反轉。
方法2：使用三個指針遍歷單鏈表，逐個鏈接點進行反轉。
方法3：從第2個節點到第N個節點，依次逐節點插入到第1個節點(head節點)之後，最後將第一個節點挪到新表的表尾。
方法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
第三次循環。。。。。
具體代碼如下
view plain
方法3
還是先看圖，
從圖上觀察，方法是：對於一條鏈表，從第2個節點到第N個節點，依次逐節點插入到第1個節點(head節點)之後，(N-1)次這樣的操作結束之後將第1個節點挪到新表的表尾即可。
代碼如下:
view plainActList* 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;
}
附:
完整的鏈表創建，顯示，反轉代碼:
view plain//創建:用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 display
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;
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;
}
摘自：feliciafay的專欄
