題目:有一個鏈表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指針，把ABCD的next分別指向A’B’C’D’，將A’的next指針指向B，B’的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)載請注明出處。