牽著老婆滿街逛

嚴以律己,寬以待人. 三思而后行.
GMail/GTalk: yanglinbo#google.com;
MSN/Email: tx7do#yahoo.com.cn;
QQ: 3 0 3 3 9 6 9 2 0 .

統計

隨筆 - 1513
文章 - 45
評論 - 907
引用 - 0

公告

言論：
1.每日自??；
2.享受人生；
3.盡力而為；
4.堅持不懈；
5.切莫急躁；
6.慎言敏行；
7.動心忍性；
8.上善若水。

常用鏈接

留言簿(11)

隨筆分類(466)

隨筆檔案(1513)

文章分類(46)

文章檔案(45)

相冊

收藏夾(39)

搜索

積分與排名

積分 - 2533141
排名 - 2

閱讀排行榜

單向鏈表反轉

題目：已知單向鏈表的頭結點head，寫一個函數把這個鏈表逆序 ( Intel)

解答：
我們假設單向鏈表的節點如下：

template <typename T>

class list_node

{

public:

list_node * next;

T data;

};

這個題目算是考察數據結構的最基礎的題目了，有兩種方法可以解此題：

方法一：

void reverse(node*& head)

{

if ( (head == 0) || (head->next == 0) ) return;// 邊界檢測

node* pNext = 0;

node* pPrev = head;// 保存鏈表頭節點

node* pCur = head->next;// 獲取當前節點

while (pCur != 0)

{

pNext = pCur->next;// 將下一個節點保存下來

pCur->next = pPrev;// 將當前節點的下一節點置為前節點

pPrev = pCur;// 將當前節點保存為前一節點

pCur = pNext;// 將當前節點置為下一節點

}

這是一般的方法，總之就是用了幾個臨時變量，然后遍歷整個鏈表，將當前節點的下一節點置為前節點。

方法二：

node* reverse( node* pNode, node*& head)

{

if ( (pNode == 0) || (pNode->next == 0) ) // 遞歸跳出條件

{

head = pNode; // 將鏈表切斷，否則會形成回環

return pNode;

}

node* temp = reserve(pNode->next, head);// 遞歸

temp->next = pNode;// 將下一節點置為當前節點，既前置節點

return pNode;// 返回當前節點

}

這個方法是采用了遞歸算法，也就是在反轉當前節點之前先反轉其后繼節點，說白了其實就是利用函數的調用堆棧構建了一個臨時鏈表罷了，挺廢的一個算法，權當作是寫著好玩，沒有什么實在的意義。
采用此算法需要注意的是，頭結點必須要傳入的是引用，因為在遞歸跳出的時候要切斷鏈表，否則鏈表將會形成一個回環。

posted on 2009-01-06 07:10 楊粼波閱讀(5767) 評論(1) 編輯收藏引用

# re: 單向鏈表反轉 2011-01-25 16:26 Bowen

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

牽著老婆滿街逛

導航

統計

公告

常用鏈接

留言簿(11)

隨筆分類(466)

隨筆檔案(1513)

文章分類(46)

文章檔案(45)

相冊

收藏夾(39)

工具官網

技術網站

開源網站

其他窩點

收藏網站

銀行官網

友情鏈接

資源共享

搜索

積分與排名

最新評論

閱讀排行榜

單向鏈表反轉

評論

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理