• <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
            兩個方法..一樣  回復  更多評論
              
            亚洲精品乱码久久久久久久久久久久 | 久久精品无码午夜福利理论片| 久久久久久久久66精品片| 亚洲精品无码久久毛片| 亚洲国产美女精品久久久久∴| 69SEX久久精品国产麻豆| 久久九色综合九色99伊人| 久久只有这里有精品4| 久久精品一本到99热免费| 94久久国产乱子伦精品免费| 一本综合久久国产二区| 久久91精品国产91久久麻豆| 香蕉aa三级久久毛片| 国产欧美久久久精品| 国产精品久久久久久久app| 1000部精品久久久久久久久| 久久久国产亚洲精品| 国产成人精品久久综合| 亚洲AV无码久久精品蜜桃| 久久精品国产色蜜蜜麻豆 | 久久久久久免费一区二区三区| 99精品国产免费久久久久久下载| 久久国产精品-国产精品| 久久亚洲精品成人AV| 麻豆精品久久久久久久99蜜桃 | 久久久久人妻一区精品| 国产午夜久久影院| 久久99国产精品尤物| 久久精品国产2020| 少妇熟女久久综合网色欲| 久久精品国产精品亚洲下载| 国产精品久久久久久久久| 亚洲狠狠婷婷综合久久蜜芽| 无码国内精品久久综合88| 亚洲国产婷婷香蕉久久久久久| 久久av免费天堂小草播放| 久久精品国产精品亚洲艾草网美妙| 免费观看成人久久网免费观看| 97久久香蕉国产线看观看| 国产精品久久久天天影视| 97精品伊人久久大香线蕉app |