當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

图理解单链表的反转

發布時間：2025/4/16 编程问答 14 豆豆

生活随笔收集整理的這篇文章主要介紹了图理解单链表的反转小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

如何把一個單鏈表進行反轉？

方法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

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;??????

}??

方法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; }
?

總結

以上是生活随笔為你收集整理的图理解单链表的反转的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

链表