用下一個和隨機指針複製一個鏈表，在列表中只給出讀取權限

Question

我需要用下一個和隨機指針複製一個鏈表。下一個指針和通常一樣指向鏈表中的下一個元素，隨機指針可能指向任何其他節點，甚至指向其自身。 如果我不允許在任何時候修改給定的列表，那麼如何完成這項工作，只列出閱讀權限。

Answer 1

最簡單的解決辦法是這樣的......

您遍歷原來的鏈表，創建另一個鏈表，其節點是一樣的，在最初的名單，在適當的next指針，指向新列表的相應節點。您現在保留random指針。

在遍歷列表時，您還將舊列表的節點地址/指針和新列表的節點地址/指針放到associative array（AKA映射，散列表等）中，其中舊列表的節點地址/指針是key，新列表的節點地址/指針是value。

然後就遍歷新的列表以及與所述value從對應於key等於random指針關聯數組的每個節點替換random指針。

散列表可以用作關聯數組來實現與原始列表中元素數量成比例的時間和內存成本。

時間&該解決方案的空間複雜度分別爲O（n）。

Answer 2

struct node * copy(struct node * head) 
{ 
    struct node *dummy; 
    struct node *dummy1=dummy; 
    struct node *head1=head; 

    struct node *map[1000000]; 
    while(head) { 
     dummy->next=new struct node; 
     map[head]=dummy->next; 
     dummy->next->data=head->data; 
     dummy=dummy->next; 
     head=head->next 
    } 
    dummy=dummy1; 
    head=head1; 
    while(head){ 
     dummy->next->arb=map[head->arb]; 
     dummy=dummy->next; 
     head=head->next; 
    } 
    return dummy1->next; 
} 

Answer 3

優雅溶液（線性時間，常數空間）：

創建節點1，2，3的副本... n和1和2,2和3等之間插入它們，忽略現在爲random字段。因此列表中總共有2n個節點。

現在的單程設置random字段的值，在新的節點通過以下方式：

original.next.random = original.random.next 

這工作，因爲LHS是在新創建的節點的random領域，RHS是指向任意節點的副本，正是我們想要的。

現在通過一次性恢復原始鏈接列表並返回新列表。

original.next = original.next.next; 
copy.next = copy.next.next; 

溶液從here.

Answer 4

#include<stdlib.h> 
#include<stdio.h> 

typedef struct node_s{ 
int data; 
struct node_s *next; 
struct node_s *arbit; 
} Node_s; 

void free_list(Node_s * head){ 
if(!head) return; 
Node_s * temp = head; 
Node_s * next = head; 
while(temp){ 
    next = temp->next; 
    free(temp); 
    temp = next; 
} 
} 
void push_1(Node_s **head, int value){ 
if(*head == NULL){ 
    (*head) = (Node_s *)malloc(sizeof(Node_s)); 
    (*head)->data = value; 
    (*head)->next = NULL; 
} 
else{ 
    Node_s * temp = (Node_s *)malloc(sizeof(Node_s)); 
    if(temp){ 
     temp->data = value; 
     temp->next = (*head); 
     *head = temp; 
    } 
} 
} 
void add_arbit(Node_s *L1, int a, int b){ 
Node_s * first = L1; 
Node_s * second = L1; 

while(first){ 
    if(first->data == a) 
     break; 
    first = first->next; 
} 
while(second){ 
    if(second->data == b) 
     break; 
    second = second->next; 
} 
if(first) 
    first->arbit = second; 
} 
Node_s * create_node(int val){ 

Node_s * temp = (Node_s *)malloc(sizeof(Node_s)); 
if(temp){ 
    temp->data = val; 
    temp->next = NULL; 
} 
return temp; 
} 

Node_s * clone(Node_s * node){ 

if(!node) return NULL; 
Node_s * current = node; 

//First insert clone nodes in original linked list.  
while(current){ 
    Node_s * current_next = current->next; 
    current->next = create_node(current->data); 
    current->next->next = current_next; 
    current = current_next; 
} 
current = node; 

//Now copy arbit pointer of each node to cloned list 
Node_s * clone_head = current->next; 
while(current){ 
    Node_s * clone = current->next; 
    if(current->arbit){ 
     clone->arbit = current->arbit->next; 
    } 
    current = clone->next; 
} 

current = node; 

//Segregate two linked list 
while(current){ 
    Node_s * clone = current->next; 
    current->next = clone->next; 
    if(clone->next){ 
     clone->next = clone->next->next; 
    } 
    current = current->next; 
} 
//return head pointer to the calling function 
return clone_head; 
} 

int main(){ 
Node_s * L1 = NULL; 
push_1(&L1,1); 
push_1(&L1,2); 
push_1(&L1,3); 
push_1(&L1,4); 
push_1(&L1,5); 
push_1(&L1,6); 

add_arbit(L1,1,6); 
add_arbit(L1,2,5); 
add_arbit(L1,3,1); 
add_arbit(L1,4,2); 
add_arbit(L1,5,4); 
add_arbit(L1,6,3); 

print_list_1(L1); 

Node_s *clone_head = clone(L1); 
free_list(L1); 
print_list_1(clone_head); 

return 0;  
} 

Answer 5

這裏採取的是遞歸的解決方案（在Java中）：

public class Solution { 

    public HashMap<RandomListNode, RandomListNode> createdNode; 
    public RandomListNode copyRandomList(RandomListNode head) { 
     createdNode = new HashMap<RandomListNode, RandomListNode>(); 
     return cc(head); 
    } 

    private RandomListNode cc(RandomListNode node) { 
     if(node == null) 
     { 
      return null; 
     } 

     RandomListNode newNode = new RandomListNode(node.label); 

     createdNode.put(node, newNode);   
     newNode.next = cc(node.next); 

     //now assign the random pointer 
     RandomListNode newRandom = null; 
     if(node.random != null) 
     { 
      newRandom = createdNode.get(node.random); 
     } 
     newNode.random = newRandom; 

     return newNode;  
    } 
} 

這裏是使用HashMap的（也是JAVA）的解決方案：

public class Solution{ 

    public RandomListNode copyRandomList(RandomListNode head) { 
     if(head == null) return null; 
     java.util.HashMap<RandomListNode, RandomListNode> map = new java.util.HashMap<RandomListNode, RandomListNode>(); 
     RandomListNode copiedHead = new RandomListNode(head.label); 
     map.put(head, copiedHead); 

     for(RandomListNode cur = head.next, cpLst = copiedHead; cur != null; cur = cur.next, cpLst = cpLst.next){ 
      cpLst.next = new RandomListNode(cur.label); 
      map.put(cur, cpLst.next); 
     } 
     for(RandomListNode cur = head, cpCur = copiedHead; cur != null; cur = cur.next, cpCur = cpCur.next) 
      cpCur.random = cur.random == null ? null : map.get(cur.random); 
     return copiedHead; 
    } 
} 

無只讀需求的另一種方法是可以here.

Answer 6

1. 開始從頭節點和一個
2. 創建節點的副本之一當您創建一個副本，使哈希映射原始節點的進入和複製節點作爲關鍵，價值。
3. 當我們逐個複製元素時創建一個新列表，所以我們得到了每個節點的下一個指針值。 4.然後用新列表再次遍歷原始列表以複製隨機指針。我們可以在哈希映射中獲得各個節點的隨機指針。

有關詳細說明，請訪問：http://www.dscoding.com/2016/10/copy-linked-list-with-random-pointer.html