程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 看圖理解單鏈表的反轉

看圖理解單鏈表的反轉

編輯:關於C

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

方法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
  1. ActList* ReverseList2(ActList* head)  
  2. {  
  3.     //ActList* temp=new ActList;  
  4.  if(NULL==head|| NULL==head->next) return head;      
  5.     ActList* p;  
  6.     ActList* q;  
  7.     ActList* r;  
  8.     p = head;    
  9.     q = head->next;  
  10.     head->next = NULL;  
  11.     while(q){  
  12.         r = q->next; //  
  13.         q->next = p;      
  14.         p = q; //  
  15.         q = r; //  
  16.     }  
  17.     head=p;  
  18.     return head;      
  19. }  



 

 

方法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的專欄

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved