• <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>
            ccyy's coding zone
            往前走,不要留戀路邊的風景.
            posts - 25,comments - 9,trackbacks - 0
               

            題目:有一個鏈表L,其每個節點有2個指針,一個指針next指向鏈表的下個節點,另一個random隨機指向鏈表中的任一個節點,可能是自己或者為空,寫一個程序,要求復制這個鏈表的結構并分析其復雜性

             

            解決方法一:

            O(n)的復雜度,掃面兩邊即可。

                                                                             圖【1】
            圖【1】是需要復制的鏈表


                                                                          圖【2】

            如圖【2】所示,ABCD是原來的鏈表,A’B’C’D’是復制的鏈表,第一遍掃描順序復制next指針,把ABCDnext分別指向A’B’C’D’,將A’next指針指向BB’next指針指向C,依次類推

            復制random指針: A’->random=A->random->next

            恢復:A->next=A’->next;A’->next=A’->next->next;

             

             

            解決方法二:

            也是O(n)的時間復雜度。。。


                                                                                圖【3】

             

            如圖【3】,第一次遍歷將要復制的鏈表A’ B’ C’ D’插入員鏈表中,然后再一次遍歷復制random指針:A->next->random=A->random->next;

            恢復很簡單:A->next=A->next->next;A’-next=A’->next->next;


            轉載請注明出處。

            posted on 2011-04-02 23:01 ccyy 閱讀(4754) 評論(2)  編輯 收藏 引用 所屬分類: C/C++

            FeedBack:
            # re: 一個鏈表問題:復制帶隨機指針的鏈表
            2011-04-29 17:30 | junfeng_feng
            連個方法,明明一樣啊...  回復  更多評論
              
            # re: 一個鏈表問題:復制帶隨機指針的鏈表
            2011-04-29 17:30 | junfeng_feng
            @junfeng_feng
            兩個方法..一樣  回復  更多評論
              
            久久精品国产黑森林| segui久久国产精品| 中文字幕无码久久人妻| 欧美成人免费观看久久| 日产精品久久久一区二区| 久久免费美女视频| 精品久久久无码中文字幕天天| 久久久精品久久久久影院| 久久久久久亚洲AV无码专区| 国产精品欧美亚洲韩国日本久久| 2021国产精品久久精品| 久久国产精品一区二区| 亚洲乱码日产精品a级毛片久久| 色综合久久久久无码专区 | 成人国内精品久久久久一区| A级毛片无码久久精品免费| 色婷婷综合久久久久中文| 久久AAAA片一区二区| 久久99精品久久只有精品| 亚洲美日韩Av中文字幕无码久久久妻妇 | 久久久久久毛片免费播放| 久久久精品日本一区二区三区| 国产亚洲精久久久久久无码77777| 国产福利电影一区二区三区久久老子无码午夜伦不 | 97久久精品国产精品青草| 少妇久久久久久被弄到高潮| 国产成人久久精品区一区二区| 中文字幕久久亚洲一区| 伊人久久免费视频| 狠狠色丁香久久综合五月| 国内精品综合久久久40p| 午夜精品久久久久成人| 国产亚洲美女精品久久久| 久久99精品久久久久久久不卡| 久久人人爽人人爽人人片AV高清| 久久久久综合国产欧美一区二区| 久久成人精品视频| 91精品国产综合久久精品| 国内精品久久久久影院优| 欧美黑人激情性久久| 久久综合给久久狠狠97色|