C++中的鏈表怎樣逆序輸出？

01-31

當成是棧。

題主能否更明確一下題意。鏈表是指單鏈表嗎？那樣還有點意義。。。

另外，用 STL 迭代器的，能不鬧嗎？

----------

在此謝謝 @黃夢龍的提醒。

如果僅僅是輸出，用遞歸即可：

void printReverse(ListNode *head) { if (head == nullptr) return; printReverse(head-&>next); std::cout &<&< head-&>val &<&< std::endl; }

完整的測試代碼見：https://gist.github.com/pezy/4d4416b64bfe2e1dd4b1

------------

順便還是提一句：

類似這種基本的鏈表問題，我總結過一篇文章。你可以看看：

談指神通 - SegmentFault

反向迭代器

#include & #include & #include & #include & using namespace std;


int main()

{

    list& a = { 0, 1, 2, 3, 4, 5 };

    copy( a.rbegin(), a.rend(), ostream_iterator&(cout, " ") );

return 0; }

額，，我正好寫過一個逆序列印的。用C寫的，，不知道可以幫到你不。

void reverse_list(list **pplist){ //鏈表逆轉 if(pplist==NULL||*pplist==NULL) return;


	list *current=NULL,*next=NULL;

	//原來的表頭

    current=(*pplist)-&>next;

	(*pplist)-&>next=NULL;

while(current!=NULL){ next=current-&>next; //保存下一個位置 current-&>next=*pplist; //改變指向 *pplist=current; //保存當前位置 current=next; } }

這是原文的鏈接：二哥學演算法之鏈表逆轉

struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ListNode* reverse_list(ListNode *head) { if (NULL == head || NULL == head-&>next) return head; ListNode *p = head; ListNode *q = p-&>next; ListNode *r; p-&>next = NULL; while (q != NULL) { r = q-&>next; q-&>next = p; p = q; q = r; } return p; }

這只是逆序，自己輸出吧,O(1)空間，別人說的遞歸壓棧都是O(n)

米有實際應用過，可以試試寫個遞歸

最好是尾遞歸

如果面試官只要求列印，一般不改動鏈表結構為好，如果要求改變鏈表的方向，則需要改變結構，再順序列印。

方法：只逆序列印，不改變結構。利用棧的後進先出來實現逆序。

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public: vector& printListFromTailToHead(ListNode* head) { vector& res;


        if(head==NULL) return res;

stack & s; ListNode *cur=head; while(head!=NULL) { s.push(head-&>val); head=head-&>next; } while(!s.empty()){ res.push_back(s.top()); s.pop(); } return res; } };

1.先反轉鏈表再遍歷輸出

2.遞歸

3.用棧

一直方法是遞歸，另一種是像stack一樣，從頂到到底pop

1. 用三根指針標記鏈中起始的連續三個元素

2. 標記鏈頭為鏈尾

3. 把第二根指針所指元素的指針置為第一根針所指元素

4. 如第三根針指向鏈尾則結束，否則三根針整體向前挪一步，回到3

當然如果你有足夠的空間，壓進棧再POP出來就行了。效率上壓棧是2N，三根針貌似是N，但每一步要做的操作多於壓棧法，所以三根針是用時間換空間。

為什麼樓上都寫的那麼複雜。。。

如果用stl里的list的話就從--end()到begin()倒序循環啊

不然就是一個stack。。

遞歸or棧，其實想想就會明白，也就是我們先訪問到的要後輸出。

1-簡單的，最好理解的就是將其轉換到數組中，然後逆序輸出數組

2-將鏈表逆序，這個經常遇到嘛，對於鏈表a-b-c-d head-&>next = b,a-&>next=c;b-&>next=a……不明白的話，搜索一下一大堆呢！

3-那不就好了嘛，想想數據結構中又沒有適合的，喲，這不是老相識棧嗎！

4-遞歸大法好……默念……