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

            久久一日本道色综合久久| 亚洲AV无码久久寂寞少妇| 久久综合精品国产二区无码| 国产成人精品久久亚洲高清不卡 | 狠狠色狠狠色综合久久| 亚洲精品视频久久久| 久久精品人妻一区二区三区| 国产精品永久久久久久久久久| 国产精品久久久久久影院| 99re这里只有精品热久久| 精品无码久久久久久午夜| 色8久久人人97超碰香蕉987| 日韩精品久久久久久久电影蜜臀| 中文字幕乱码人妻无码久久| 欧美亚洲色综久久精品国产| 久久久久久久久无码精品亚洲日韩| 无码国内精品久久人妻| 国内精品久久人妻互换| 99久久精品国产高清一区二区| 99久久这里只有精品| 亚洲国产精品久久久久婷婷老年 | 国产99久久久国产精免费| 国内精品久久久久久久涩爱 | 久久av免费天堂小草播放| 色综合久久天天综线观看| 久久精品国产亚洲AV影院| 日日躁夜夜躁狠狠久久AV| 久久久久久免费一区二区三区| 精品一久久香蕉国产线看播放| 久久久久亚洲爆乳少妇无| 漂亮人妻被中出中文字幕久久| av色综合久久天堂av色综合在| 韩国免费A级毛片久久| 久久97久久97精品免视看| 久久福利资源国产精品999| 久久成人国产精品| 亚洲国产精品综合久久一线| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 久久精品国产亚洲AV香蕉| 精品久久久无码中文字幕| 久久久噜噜噜久久|