最后將原頭節(jié)點變?yōu)槲补?jié)點，尾節(jié)點變?yōu)轭^節(jié)點。
單向鏈表的反轉(zhuǎn)是一個經(jīng)常
被問到的一個面試題，也是一個非?；A的問題。比如一個鏈表是這樣的： 1->2->3->4->5 通過反轉(zhuǎn)后成為5->4->3->2->1。最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當前指針指向的下一個元素，然后將當前節(jié)點元素的指針反轉(zhuǎn)后，利用已經(jīng)存儲的指針往后面繼續(xù)遍歷。源代碼如下：
struct linka { int data; linka* next;};void reverse(linka*& head){ if(head ==NULL) return; linka*pre, *cur, *ne; pre=head; cur=head->next; while(cur) { ne = cur->next;// 保留后面節(jié)點信息 cur->next = pre; // 改變前驅(qū)后繼關系 pre = cur;// 兩個指針平移 cur = ne; } head->next = NULL; head = pre;}
解釋：對于頭結點后的下一個結點cur如果不為空，則得到它的下一個結點保存在ne結點中，然后把cur的下一個結點賦為cur的前一個結點pre，這樣就實現(xiàn)了cur和它的前一個結點的交換，然后把cur結點賦給pre結點，把ne結點賦給cur，這就實現(xiàn)了cur結點和pre結點都向后移了一個結點，然后循環(huán)下去，一直到cur結點為空時，說明已到鏈表尾，這時把頭結點的后一個結點指向空，說明頭結點已經(jīng)成了尾結點了，這個時候把pre結點已經(jīng)是原鏈表的最尾端了，如果要實現(xiàn)翻轉(zhuǎn)，則把它賦給頭結點。
如上圖所示，它是先翻轉(zhuǎn)head和p1,使p1指向head,然后pre=cur;cur=ne;到第二次，繼續(xù)翻轉(zhuǎn)p1,p2,使p2指向p1,然后持續(xù)下去，一直到第四次，這時cur為空，而pre已到了原鏈表的最后一個結點，這時如果head的下一個結點為空，則說明head為鏈尾了，而pre則變成了鏈頭，然后把它賦給頭結點即可。
