生活随笔
收集整理的這篇文章主要介紹了
C++实现链表逆序打印、链表反转
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
//題目：C++實(shí)現(xiàn)鏈表逆序打印、鏈表反轉(zhuǎn)
// 如何將鏈表逆序，取決于題目的要求。如果面試官只要求打印，一般不改動鏈表結(jié)構(gòu)為好，如果要求改變鏈表的方向，則需要改變結(jié)構(gòu)，再順序打印。
// 方法1：只逆序打印，不改變結(jié)構(gòu)。采用遞歸，到達(dá)尾結(jié)點(diǎn)時(shí)打印輸出，否則進(jìn)入下一個(gè)結(jié)點(diǎn)的遞歸，當(dāng)遞歸一層層退出的時(shí)候，便可以實(shí)現(xiàn)從尾到頭的打印。
// 方法2：頭插法，改變結(jié)構(gòu)。從第二個(gè)結(jié)點(diǎn)開始往后，依次把每個(gè)結(jié)點(diǎn)移至鏈表頭部，要注意最后鏈表不要是斷裂的。
// 方法3：改變指針方向。從頭結(jié)點(diǎn)開始，依次把結(jié)點(diǎn)的next指針斷開指向該結(jié)點(diǎn)的前結(jié)點(diǎn)。要注意保存好，前結(jié)點(diǎn)、當(dāng)前結(jié)點(diǎn)和下一個(gè)結(jié)點(diǎn)。
// 方法4：只逆序打印，不改變結(jié)構(gòu)。利用棧的后進(jìn)先出來實(shí)現(xiàn)逆序。
//
// 注意：鏈表為空、鏈表只有一個(gè)結(jié)點(diǎn)的情況
// 完整代碼如下：
#include<iostream>
#include <stack>
using namespace std;
struct ListNode
{ int value; ListNode *next;
};
void ReversePrint(ListNode *pHead)//遞歸實(shí)現(xiàn)逆序打印（不改變鏈表結(jié)構(gòu)）
{ if(pHead!=NULL) { if(pHead->next!=NULL) ReversePrint(pHead->next); cout<<pHead->value<<" "; }
}
ListNode *ReverseList1(ListNode *pHead)//頭插法（改變鏈表結(jié)構(gòu)）
{ if(pHead==NULL) return NULL; ListNode *p=pHead->next; ListNode *newHead=pHead; while(p!=NULL) //將p結(jié)點(diǎn)移到鏈表最前方 { pHead->next=p->next;//頭結(jié)點(diǎn)指向p的下一個(gè)結(jié)點(diǎn) p->next=newHead; //p插入鏈表最前方 newHead=p; //鏈表新頭結(jié)點(diǎn)更新為p p=pHead->next;//處理下一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)位于頭結(jié)點(diǎn)后 } return newHead;
}
ListNode *ReverseList2(ListNode *pHead)//依次改變指針方向（改變鏈表結(jié)構(gòu)）
{ ListNode *pre=NULL; ListNode *p=NULL; while(pHead!=NULL){ p=pHead->next; //保存剩余鏈表 pHead->next=pre;//斷開剩余鏈表頭結(jié)點(diǎn)pHead，指向pre pre=pHead; //pre更新 pHead=p; //head更新 } return pre;
} int main()//主函數(shù)
{ int n; cin>>n; //輸入元素個(gè)數(shù) ListNode* head=NULL; ListNode* p=NULL; ListNode* q=NULL; for(int i=0;i<n;i++)//分配內(nèi)存，依次輸入元素 { q=new ListNode; cin>>q->value; if(head==NULL) { head=q; p=head; } else { p->next=q; p=p->next; } } if(head==NULL) return 0; p->next=NULL; //驗(yàn)證 cout<<"遞歸逆序打印: "<<endl; ReversePrint(head); cout<<endl<<"頭插法反轉(zhuǎn)鏈表: "<<endl; ListNode* reverseHead; reverseHead = ReverseList1(head); p=reverseHead; while(p!=NULL) { cout<<p->value<<" "; p=p->next; } cout<<endl<<"改變指針方向反轉(zhuǎn)鏈表（將鏈表再次反轉(zhuǎn)）: "<<endl; p = ReverseList2(reverseHead); //改變指針方向反轉(zhuǎn)鏈表 while(p!=NULL) { cout<<p->value<<" "; q=p; p=p->next; delete q;//釋放內(nèi)存 } cout<<endl; return 0;
} //方法4：利用一個(gè)棧
void printListFromTailToHead(ListNode *pHead)
{ stack<ListNode*> nodes; ListNode *p=pHead; while(p!=NULL) { nodes.push(p);//入棧 p=p->next; } while(!nodes.empty()) { p=nodes.top();//賦值 cout<<p->value<<endl; nodes.pop();//刪除棧頂元素 }
}
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎
總結(jié)
以上是生活随笔為你收集整理的C++实现链表逆序打印、链表反转的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
