當前位置:網站首頁>複制帶隨機指針的鏈錶<難度系數>

複制帶隨機指針的鏈錶<難度系數>

2022-05-15 02:10:57華為雲

題述:給你一個長度為 n 的鏈錶,每個節點包含一個額外增加的隨機指針 random ,該指針可以指向鏈錶中的任何節點或空節點。
構造這個鏈錶的深拷貝。 深拷貝應該正好由 n 個全新節點組成,其中每個新節點的值都設為其對應的原節點的值。
新節點的 next 指針和 random 指針也都應指向複制鏈錶中的新節點,並使原鏈錶和複制鏈錶中的這些指針能够錶示相同的鏈錶狀態。複制鏈錶中的指針都不應指向原鏈錶中的節點 。

例如,如果原鏈錶中有 X 和 Y 兩個節點,其中 X.random --> Y 。那麼在複制鏈錶中對應的兩個節點 x 和 y ,同樣有 x.random --> y 。返回複制鏈錶的頭節點。
用一個由 n 個節點組成的鏈錶來錶示輸入/輸出中的鏈錶。每個節點用一個 [val, random_index] 錶示:
val:一個錶示 Node.val 的整數。
random_index:隨機指針指向的節點索引(範圍從 0 到 n-1);如果不指向任何節點,則為 null 。
你的代碼只接受原鏈錶的頭節點 head 作為傳入參數。

示例1:
在這裏插入圖片描述

輸入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2:
在這裏插入圖片描述

輸入:head = [[1,1],[2,1]]
輸出:[[1,1],[2,1]]

示例3:
在這裏插入圖片描述
輸入:head = [[3,null],[3,0],[3,null]]
輸出:[[3,null],[3,0],[3,null]]

示例4:
輸入:head = [ ]
輸出:[ ]

🧷 平臺:Visual studio 2017 && windows

核心思想:
思路一 (不實現):1,先複制原鏈錶的每個節點,再把新節點鏈接起來 (拷貝節點與原節點沒有建立關系);2,計算原鏈錶中的每個節點cur的random跟cur的相對距離;3,再去複制新鏈錶中找到當前節點相對距離的節點,賦值給random;找1個節點的random的時間複雜度是O(N),找所有節點的random的時間複雜度是O(N^2)

思路二 (優化思路一):1,在原鏈錶的每個節點的後面,鏈接插入一個拷貝節點 (建立相對關系,找random);2,置random;3,把拷貝節點解下來,鏈接到一起,同時恢複原鏈錶;時間複雜度是O(N)

請添加圖片描述

leetcode原題

#include<stdio.h>#include<stdlib.h>struct Node{	int val;	struct Node* next;	struct Node* random;};struct Node* copyRandomList(struct Node* head){	if(head == NULL)        return NULL;	//1.拷貝節點至每個原節點的後面    struct Node* cur = head;    while(cur)    {        //先保存下一個節點的地址        struct Node* next = cur->next;        //開避拷貝節點的空間        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));        //要保證val是相同的        copy->val = cur->val;        //修改原鏈錶的鏈接關系        cur->next = copy;        copy->next = next;        //迭代        cur = next;    }       //2.置random    cur = head;    while(cur)    {        //找拷貝節點        struct Node* copy = cur->next;        //鏈接random,當cur的random為空時,需要特殊處理        if(cur->random)            copy->random = cur->random->next;        else            copy->random = NULL;        //迭代        cur = copy->next;    }    //3.把拷貝節點解下來,尾插至新鏈錶(使用帶哨兵比特的頭節點)。順手複原原鏈錶,雖然題意並沒有要求    struct Node *copyhead, *copytail;    copyhead = copytail = (struct Node*)malloc(sizeof(struct Node));    cur = head;    while(cur)    {        //找拷貝節點        struct Node* copy = cur->next;         //保存原鏈錶的下一個節點的地址        struct Node* next = copy->next;        //尾插        copytail->next = copy;        copytail = copy;        //恢複原鏈錶        cur->next = next;        //迭代        cur = next;    }    //4.釋放空間    struct Node* temp = copyhead;    copyhead = copyhead->next;    free(temp);    return copyhead;}int main(){	struct Node* n1 = (struct Node*)malloc(sizeof(struct Node));	n1->val = 3;	struct Node* n2 = (struct Node*)malloc(sizeof(struct Node));	n2->val = 3;		struct Node* n3 = (struct Node*)malloc(sizeof(struct Node));	n3->val = 3;	n1->next = n2;	n2->next = n3;	n3->next = NULL;		n1->random = n3;	n2->random = n1;	n3->random = NULL;		copyRandomList(n1);	return 0;}

請添加圖片描述

版權聲明
本文為[華為雲]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/135/202205142058343961.html

隨機推薦