題目:有一個(gè)鏈表L,其每個(gè)節(jié)點(diǎn)有2個(gè)指針，一個(gè)指針next指向鏈表的下個(gè)節(jié)點(diǎn)，另一個(gè)random隨機(jī)指向鏈表中的任一個(gè)節(jié)點(diǎn)，可能是自己或者為空，寫一個(gè)程序，要求復(fù)制這個(gè)鏈表的結(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)的時(shí)間復(fù)雜度。。。

                                                                    圖【3】

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

恢復(fù)很簡(jiǎn)單：A->next=A->next->next;A’-next=A’->next->next;


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