• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            


            牽著老婆滿街逛
            

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

            




            
	
					
	
            
		
            
			單向鏈表反轉
		
            
		題目：已知單向鏈表的頭結點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 楊粼波 閱讀(5758) 評論(1)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    


            

            評論
            
	
	
			
            
				# re: 單向鏈表反轉
					
						2011-01-25 16:26
					
				Bowen
			
            
			
            
				方法一沒有寫完吧，不然傳head指針和他的指針引用就沒有區別了
            head->next = NULL;
            head = pPrev;  回復  更多評論
				  
			
            
		

            




            






            

				

            



    
    







            
	   
	



国产欧美一区二区久久|
99久久国产宗和精品1上映
|
久久91综合国产91久久精品|
亚洲成人精品久久|
中文字幕无码av激情不卡久久|
精品久久久久久中文字幕大豆网|
国产V亚洲V天堂无码久久久|
欧美性大战久久久久久|
俺来也俺去啦久久综合网|
亚洲另类欧美综合久久图片区|
久久精品国产清高在天天线|
久久婷婷五月综合成人D啪|
久久精品99久久香蕉国产色戒|
国产无套内射久久久国产|
蜜臀av性久久久久蜜臀aⅴ麻豆|
狠狠人妻久久久久久综合|
久久亚洲AV成人无码国产|
午夜福利91久久福利|
夜夜亚洲天天久久|
久久久国产乱子伦精品作者|
亚洲伊人久久综合中文成人网|
99久久久久|
久久夜色精品国产亚洲|
国产欧美久久久精品|
国产精品无码久久综合|
久久青青草原亚洲av无码app|
久久青青草视频|
久久影视综合亚洲|
久久涩综合|
亚洲欧美日韩精品久久亚洲区|
久久国产热这里只有精品|
国产精品青草久久久久福利99|
亚洲国产成人久久精品动漫|
久久91亚洲人成电影网站|
久久久久四虎国产精品|
久久精品国产半推半就|
久久国产精品免费一区二区三区|
日本免费一区二区久久人人澡|
91精品日韩人妻无码久久不卡
|
久久性精品|
欧美一区二区久久精品|