劍指offer 複雜連結串列的複製

2022-11-24 15:01:40 字數 1485 閱讀 4494

輸入一個複雜連結串列(每個節點中有節點值,以及兩個指標,一個指向下一個節點,另一個特殊指標指向任意一個節點),返回結果為複製後複雜連結串列的head。(注意,輸出結果中請不要返回引數中的節點引用,否則判題程式會直接返回空)

1

struct

randomlistnode

7 };

解法一:

2、設定每個節點的random指標。假設原始連結串列的某個節點n的random指向節點s,由於s在連結串列中可能在n的前面也可能在n的後面,所以要定位s的位置需要從原始連結串列的頭結點開始找。如果從原始連結串列的頭結點沿著next經過s步找到節點s,那麼在複製連結串列上節點n'的random(記為s')離複製連結串列的頭結點的距離也是沿著next指標s步。用這種方法可以為複製連結串列上的每個節點設定random指標。

時間複雜度分析:對於一個有n個節點的連結串列,由於定位每個節點的random都需要從連結串列頭結點開始經過 o(n)才能找到。因此總的時間複雜度為o(n2)

解法二:解法一的時間主要花費在定位節點的random上面。為此,我們分為兩步:

第一,複製原始連結串列上的每一個節點n建立n',然後把這些建立出來的節點用next連結起來, 同時我們把配對資訊儲存到一個雜湊表中;

第二,設定每個節點的random。如果原始連結串列節點n的random為s, 那麼在複製連結串列中n'的random應該指向s'. 第一步中,我們儲存了, .

1/*2

struct randomlistnode 8};

9*/10class

solution

23 tmp =phead;

24for (map::iterator it = mp.begin(); it != mp.end(); it++)

28return res->next;29}

30 };

以空間換時間, o(n)的空間複雜度,o(n)的時間複雜度

解法三:

1/*2

struct randomlistnode 8};

9*/10class

solution

2425 pcurrent =phead;

26while (pcurrent !=null)

32 randomlistnode* pnode =phead;

33 randomlistnode* pclonedhead = pnode->next;

34 randomlistnode* pclonednode = pnode->next;

3536 pnode->next = pclonednode->next;

37 pnode = pclonednode->next;

38while (pnode !=null)

44return

pclonedhead;45}

46 };

劍指offer 字串的排序

輸入一個字串,按字典序列印出該字串中字元的所有排列。例如輸入字串abc,則列印出由字元a,b,c所能排列出來的所有字串abc,acb,bac,bca,cab和cba。輸入一個字串,長度不超過9 可能有字元重複 字元只包括大小寫字母。從首位開始,每一個位置都從1,2,3分別取值,只當前位優先取當前剩餘...

字串的排列 劍指offer

輸入一個字串,按字典序列印出該字串中字元的所有排列。例如輸入字串abc,則列印出由字元a,b,c所能排列出來的所有字串abc,acb,bac,bca,cab和cba。利用回溯法迴圈 圖為網路查詢 以abc為例 public class solution public void fun arrayli...

劍指offer 面試的流程

對於初級程式設計師來說,我一般會偏向考察她的一些基本功,比如 資料結構啦,演算法啦 但是對於高階程式設計師來說,我一般會偏向於考察她的一些專案經驗啦,處理問題的一個思路啦,還有她的一些管理經驗這種東西。應聘的人,首先要做好足夠的準備,如果在面試的時候,能夠說出一些面試公司的近況 對專案的情況有的瞭解...