|
一次遍歷鏈表，原地改變鏈表。不占用額外資源。 原理：不斷的將前后兩個節(jié)點的前驅(qū)和后繼關(guān)系改變方向。最后將原頭節(jié)點變?yōu)槲补?jié)點，尾節(jié)點變?yōu)轭^節(jié)點。
單向鏈表的反轉(zhuǎn)是一個經(jīng)常 被問到的一個面試題，也是一個非?；A(chǔ)的問題。比如一個鏈表是這樣的： 1->2->3->4->5 通過反轉(zhuǎn)后成為5->4->3->2->1。最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當(dāng)前指針指向的下一個元素，然后將當(dāng)前節(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ū)后繼關(guān)系
pre = cur;// 兩個指針平移
cur = ne;
}
head->next = NULL;
head = pre;
}
解釋：對于頭結(jié)點后的下一個結(jié)點cur如果不為空，則得到它的下一個結(jié)點保存在ne結(jié)點中，然后把cur的下一個結(jié)點賦為cur的前一個結(jié)點pre，這樣就實現(xiàn)了cur和它的前一個結(jié)點的交換，然后把cur結(jié)點賦給pre結(jié)點，把ne結(jié)點賦給cur，這就實現(xiàn)了cur結(jié)點和pre結(jié)點都向后移了一個結(jié)點，然后循環(huán)下去，一直到cur結(jié)點為空時，說明已到鏈表尾，這時把頭結(jié)點的后一個結(jié)點指向空，說明頭結(jié)點已經(jīng)成了尾結(jié)點了，這個時候把pre結(jié)點已經(jīng)是原鏈表的最尾端了，如果要實現(xiàn)翻轉(zhuǎn)，則把它賦給頭結(jié)點。
如上圖所示，它是先翻轉(zhuǎn)head和p1,使p1指向head,然后pre=cur;cur=ne;到第二次，繼續(xù)翻轉(zhuǎn)p1,p2,使p2指向p1,然后持續(xù)下去，一直到第四次，這時cur為空，而pre已到了原鏈表的最后一個結(jié)點，這時如果head的下一個結(jié)點為空，則說明head為鏈尾了，而pre則變成了鏈頭，然后把它賦給頭結(jié)點即可。 C#版本 //鏈表翻轉(zhuǎn) public void Reverse() { Node<int> p = head; Node<int> q = head.Next； Node<int> r = new Node<int>(); while(q!= null) { r = q.Next; q.Next = p; p=q; q = r; } head.Next = null; head = p; } |
|
|
