單鏈表實現(xiàn)反轉的3種方法示例代碼
更新時間：2019年02月11日 11:03:10 作者：攻城猿bilibili
單鏈表的反轉是常見的面試題目，下面這篇文章主要給大家介紹了關于單鏈表實現(xiàn)反轉的3種方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧
前言
單鏈表的操作是面試中經常會遇到的問題，今天總結一下反轉的幾種方案：
1 ，兩兩對換
2， 放入數(shù)組，倒置數(shù)組
3， 遞歸實現(xiàn)
代碼如下：
#include<stdio.h>
#include<malloc.h>
typedef struct Node
{
int data;
struct Node *pnext;
} Node,*pnode;
pnode CreateNode()
{
pnode phead=(pnode)malloc(sizeof(Node));
if(phead==NULL)
{
printf("fail to allocate memory");
return -1;
}
phead->pnext=NULL;
int n;
pnode ph=phead;
for(int i=0; i<5; i++)
{
pnode p=(pnode)malloc(sizeof(Node));
if(p==NULL)
{
printf("fail to allocate memory");
return -1;
}
p->data=(i+2)*19;
phead->pnext=p;
p->pnext=NULL;
phead=phead->pnext;
}
return ph;
}
int list(pnode head)
{
int count=0;
printf("遍歷結果：\n");
while(head->pnext!=NULL)
{
printf("%d\t",head->pnext->data);
head=head->pnext;
count++;
}
printf("鏈表長度為：%d\n",count);
return count;
}
pnode reverse2(pnode head)//兩兩節(jié)點之間不斷交換
{
if(head == NULL || head->next == NULL)
return head;
pnode pre = NULL;
pnode next = NULL;
while(head != NULL){
next = head->next;
head->next = pre;
pre = head;
head = next;
}
return pre;
}
void reverse1(pnode head,int count)//把鏈表的節(jié)點值放在數(shù)組中，倒置數(shù)組
{
int a[5]= {0};
for(int i=0; i<count,head->pnext!=NULL; i++)
{
a[i]=head->pnext->data;
head=head->pnext;
}
for(int j=0,i=count-1; j<count; j++,i--)
printf("%d\t",a[i]);
}
pnode reverse3(pnode pre,pnode cur,pnode t)//遞歸實現(xiàn)鏈表倒置
{
cur -> pnext = pre;
if(t == NULL)
return cur; //返回無頭節(jié)點的指針，遍歷的時候注意
reverse3(cur,t,t->pnext);
}
pnode new_reverse3(pnode head){ //新的遞歸轉置
if(head == NULL || head->next == NULL)
return head;
pnode new_node = new_reverse3(head->next);
head->next->next = head;
head->next = NULL;
return new_node; //返回新鏈表頭指針
}
int main()
{
pnode p=CreateNode();
pnode p3=CreateNode();
int n=list(p);
printf("1反轉之后：\n");
reverse1(p,n);
printf("\n");
printf("2反轉之后：\n");
pnode p1=reverse2(p);
list(p1);
p3 -> pnext = reverse3(NULL,p3 -> pnext,p3->pnext->pnext);
printf("3反轉之后：\n");
list(p3);
free(p);
free(p1);
free(p3);
return 0;
}
毫無疑問，遞歸是解決的最簡單方法，四行就能解決倒置問題。
思路參考：http://www.dhdzp.com/article/156043.htm
這里注意： head ->next = pre; 以及 pre = head->next，前者把head->next 指向 pre，而后者是把head->next指向的節(jié)點賦值給pre。如果原來head->next 指向 pnext節(jié)點，前者則是head重新指向pre，與pnext節(jié)點斷開，后者把pnext值賦值給pre，head與pnext并沒有斷開。
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對腳本之家的支持。
相關文章
這篇文章主要為大家詳細介紹了C++修改const變量，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
C++?Qt開發(fā)之使用QNetworkAccessManager實現(xiàn)Web網(wǎng)頁訪問
Qt?是一個跨平臺C++圖形界面開發(fā)庫,利用Qt可以快速開發(fā)跨平臺窗體應用程序,本文主要介紹了如何運用QNetworkAccessManager組件實現(xiàn)Web網(wǎng)頁訪問,需要的可以參考下2024-03-03
遲早一定會掛掉的俄羅斯方塊，為什么至今仍是世界游戲之王？它是怎么編寫的？本文將給大家詳細介紹六種模式的實現(xiàn)，對大家的學習或工作具有一定的參考借鑒價值2022-02-02
下面小編就為大家?guī)硪黄钊肜斫鈉++指針的指針和指針的引用。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考，一起跟隨小編過來看看吧2021-09-09
今天小編就為大家分享一篇關于C++命名空間namespace的介紹與使用，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
C語言提供了malloc和free兩個系統(tǒng)函數(shù),完成對堆內存的申請和釋放,而C++則提供了兩個關鍵字new和delete,下面這篇文章主要給大家介紹了如何通過一篇文章了解c++中new和delete的相關資料,需要的朋友可以參考下2021-12-12
在之前的C++代碼訓練營系列中，我試圖用完成具體項目的方式給大家介紹C++，但后來大家反饋說這樣從C過渡到C++有點跟不上。于是我又專門設計了這個《從C到C++》的過渡專題，我準備通過10篇文章介紹一下C++和C的重要區(qū)別。2017-07-07
這篇文章主要介紹了C語言實現(xiàn)SM4加解密方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-04-04
下面小編就為大家?guī)硪黄钊肜斫釩++移位運算符。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-05-05
QtCharts 組件是QT中提供圖表繪制的模塊，用來繪制常規(guī)圖形，本文就詳細的介紹了QChart的使用，以及柱狀圖，折線圖等常用的圖形的實現(xiàn)，感興趣的可以了解一下2021-11-11