• <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;  回復  更多評論
				  
			
            
		

            




            






            

				

            



    
    







            
	   
	



A级毛片无码久久精品免费|
久久这里的只有是精品23|
av无码久久久久久不卡网站|
一级做a爰片久久毛片16|
久久无码一区二区三区少妇|
国内精品久久久久影院优|
国产69精品久久久久777|
亚洲综合伊人久久综合|
久久精品欧美日韩精品|
久久久久亚洲av成人网人人软件|
久久国产精品视频|
久久伊人精品一区二区三区|
久久久这里有精品中文字幕|
亚洲色婷婷综合久久|
91久久香蕉国产熟女线看|
一本久久精品一区二区|
久久性精品|
久久99国产精一区二区三区|
99久久99久久精品免费看蜜桃|
狠狠色丁香婷婷综合久久来来去|
亚洲中文久久精品无码|
久久不见久久见免费影院www日本|
亚洲国产精品无码久久一区二区|
久久亚洲精品国产亚洲老地址|
国内精品久久国产大陆|
亚洲国产精品无码久久久不卡|
久久国产综合精品五月天|
四虎国产精品免费久久5151|
久久精品国产亚洲5555|
久久免费精品视频|
久久久久免费看成人影片|
性色欲网站人妻丰满中文久久不卡|
色偷偷91久久综合噜噜噜噜|
亚洲精品国产综合久久一线|
青青青伊人色综合久久|
久久成人精品视频|
日本免费久久久久久久网站|
伊人热人久久中文字幕|
伊人久久免费视频|
久久久久噜噜噜亚洲熟女综合|
国产精品伦理久久久久久|