劍指Offer - 九度1511 - 從尾到頭打印鏈表
2013-11-29 21:08 題目描述：

輸入一個鏈表，從尾到頭打印鏈表每個節(jié)點的值。

輸入：

每個輸入文件僅包含一組測試樣例。
每一組測試案例包含多行，每行一個大于0的整數(shù)，代表一個鏈表的節(jié)點。第一行是鏈表第一個節(jié)點的值，依次類推。當輸入到-1時代表鏈表輸入完畢。-1本身不屬于鏈表。

輸出：

對應每個測試案例，以從尾到頭的順序輸出鏈表每個節(jié)點的值，每個值占一行。

樣例輸入：

1 2 3 4 5 -1

樣例輸出：

5 4 3 2 1

題意分析：
　　給定一條單鏈表，從未到頭打印出來。第一個念頭是可以用頭遞歸的寫法進行倒序輸出，但不論頭遞歸還是尾遞歸都不是個會寫代碼的人該寫出來的，因為遞歸調用中的棧操作開銷太累，而且百萬級的數(shù)據(jù)就能搞出棧溢出了。所以可以采取先反轉鏈表，再輸出的方法。至于輸出完了要不要再轉回去，就看數(shù)據(jù)還有沒有人要用了。不過從原則上來說，既然要求設計的是逆序輸出鏈表，就不應該改變原始數(shù)據(jù)，應該在處理完了以后把鏈表給轉回來的。本題中的數(shù)據(jù)時一次性的，我索性輸出完了就給釋放掉了。
　　時間復雜度O(n)，空間復雜度O(1)。 1 // 650320 zhuli19901106 1511 Accepted 點擊此處查看所有case的執(zhí)行結果 5088KB 731B 90MS 2 // 201311122057 3 #include <cstdio> 4 #include <vector> 5 using namespace std; 6 7 class ListNode{ 8 public: 9 int val; 10 ListNode *next; 11 ListNode(int _val = 0) : val(_val), next(NULL){} 12 }; 13 14 int main() 15 { 16 ListNode *root; 17 ListNode *tail; 18 int n; 19 vector<ListNode *> vv; 20 21 root = new ListNode(); 22 tail = root; 23 vv.clear(); 24 while(scanf("%d", &n) == 1 && n >= 0){ 25 tail->next = new ListNode(n); 26 tail = tail->next; 27 vv.push_back(tail); 28 } 29 30 while(vv.size() > 0){ 31 printf("%d\n", vv[vv.size() - 1]->val); 32 vv.pop_back(); 33 } 34 35 tail = root; 36 while(tail != NULL){ 37 root = tail->next; 38 delete tail; 39 tail = root; 40 } 41 42 return 0; 43 } ?

轉載于:https://www.cnblogs.com/zhuli19901106/p/3450320.html

總結

以上是生活随笔為你收集整理的剑指Offer - 九度1511 - 从尾到头打印链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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