• <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 楊粼波 閱讀(5752) 評論(1)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    


            

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

            




            






            

				

            



    
    







            
	   
	



久久久国产精品|
亚洲色大成网站WWW久久九九|
中文字幕人妻色偷偷久久|
久久精品中文字幕一区|
久久天天躁狠狠躁夜夜不卡|
国产色综合久久无码有码|
97久久久久人妻精品专区
|
99久久99这里只有免费费精品|
…久久精品99久久香蕉国产|
国产福利电影一区二区三区，免费久久久久久久精
|
无码国产69精品久久久久网站|
久久久久久人妻无码|
国内精品久久久久久麻豆
|
国产精品久久久久…|
久久久久国产精品三级网|
婷婷五月深深久久精品|
久久有码中文字幕|
久久国产精品国产自线拍免费|
久久国产乱子伦精品免费午夜|
久久精品国产免费观看
|
午夜天堂精品久久久久|
久久久久久无码国产精品中文字幕
|
久久久久亚洲av无码专区喷水
|
久久99国产精品久久99|
国内精品伊人久久久久777|
久久国产精品免费一区|
久久96国产精品久久久|
久久精品夜夜夜夜夜久久|
亚洲欧美一级久久精品|
久久综合给合综合久久|
狠狠色伊人久久精品综合网|
九九久久自然熟的香蕉图片|
亚洲精品乱码久久久久久蜜桃图片|
久久99精品国产麻豆不卡|
久久免费美女视频|
91精品观看91久久久久久|
88久久精品无码一区二区毛片|
久久综合中文字幕|
国産精品久久久久久久|
色偷偷88欧美精品久久久|
久久精品无码一区二区三区日韩|