• <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
            往前走,不要留戀路邊的風(fēng)景.
            posts - 25,comments - 9,trackbacks - 0
               

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

             

            解決方法一:

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

                                                                             圖【1】
            圖【1】是需要復(fù)制的鏈表


                                                                          圖【2】

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

            復(fù)制random指針: A’->random=A->random->next

            恢復(fù):A->next=A’->next;A’->next=A’->next->next;

             

             

            解決方法二:

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


                                                                                圖【3】

             

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

            恢復(fù)很簡單:A->next=A->next->next;A’-next=A’->next->next;


            轉(zhuǎn)載請注明出處。

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

            FeedBack:
            # re: 一個鏈表問題:復(fù)制帶隨機指針的鏈表
            2011-04-29 17:30 | junfeng_feng
            連個方法,明明一樣啊...  回復(fù)  更多評論
              
            # re: 一個鏈表問題:復(fù)制帶隨機指針的鏈表
            2011-04-29 17:30 | junfeng_feng
            @junfeng_feng
            兩個方法..一樣  回復(fù)  更多評論
              

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            久久e热在这里只有国产中文精品99| 99久久免费国产精品特黄| 一级做a爰片久久毛片人呢| 国内精品久久久久久麻豆| 一本一道久久a久久精品综合| 一本色道久久88精品综合| 国产成人精品久久亚洲| 2021国内久久精品| 伊人久久大香线蕉影院95| 久久经典免费视频| 久久97精品久久久久久久不卡 | 亚洲国产另类久久久精品小说| 国产婷婷成人久久Av免费高清| 久久久久黑人强伦姧人妻| 久久久久亚洲av无码专区| 久久久久黑人强伦姧人妻| 久久99亚洲网美利坚合众国| 婷婷国产天堂久久综合五月| a级毛片无码兔费真人久久| 亚洲中文字幕久久精品无码喷水 | 青青青国产精品国产精品久久久久| 超级碰碰碰碰97久久久久| 久久免费精品一区二区| 久久国产精品99精品国产| 午夜精品久久久内射近拍高清| 91精品免费久久久久久久久| 99久久99久久久精品齐齐| 欧美丰满熟妇BBB久久久| 国产精品久久新婚兰兰| 中文成人无码精品久久久不卡 | 亚洲午夜久久久精品影院| 久久久久久久亚洲Av无码| 久久久精品人妻一区二区三区蜜桃| 久久精品国产福利国产琪琪| 欧美一区二区精品久久| 97久久精品人人做人人爽| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 久久精品极品盛宴观看| 久久青青草原精品国产| 精品久久久久久成人AV| 日韩精品久久无码人妻中文字幕|