skopiuj połączoną listę z następnym i losowym wskaźnikiem, tylko uprawnienia odczytu są podane na liście

Question

Muszę skopiować połączoną listę z następnym i losowym wskaźnikiem. Następny wskaźnik jak zwykle wskazuje na następny element na połączonej liście i losowy wskaźnik może wskazywać na dowolny inny węzeł lub nawet na siebie. W jaki sposób można to zrobić, jeśli nie mam uprawnień do modyfikowania podanej listy w dowolnym momencie, tylko uprawnienia do odczytu są podane na liście.

Answer 1

Najprostszym rozwiązaniem byłoby coś takiego ...

można przemierzać pierwotną listę związaną i utworzyć inną połączonej listy, którego węzły są takie same jak w pierwotnym wykazie, przy prawidłowej next wskaźników, wskazując na odpowiednie węzły nowej listy. Zachowaj wskaźniki random, jak na razie.

Podczas przewijania listy wstawia się także adres/wskaźnik węzła starej listy oraz adres/wskaźnik węzła nowej listy na associative array (mapa AKA, tablica skrótów itp.), Gdzie stary adres/wskaźnik węzła listy to key, a adres/wskaźnik węzła nowej listy to value.

Wtedy przemierzać nową listę i zastąpić wskaźnik random w każdym węźle z value z tablicy asocjacyjnej odpowiadającej key równej wskaźnik random.

Tablica asocjacyjna może być używana jako tablica asocjacyjna, aby uzyskać czas i koszt pamięci proporcjonalny do liczby elementów na oryginalnej liście.

Czas złożoności tego rozwiązania wynosi 0 (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

eleganckie rozwiązanie (czas liniowy stałą przestrzeń)

Tworzenie kopii węzła 1, 2, 3 ... n i umieścić je pomiędzy 1 i 2, 2 i 3 i tak dalej, ignorując pole random na teraz. Łącznie na liście znajduje się 2n węzłów.

teraz ustawić wartość random pól w nowych węzłów w następujący sposób z jednego przejazdu:

original.next.random = original.random.next 

To działa, ponieważ LHS jest pole w nowo utworzonego węzła random i RHS jest wskaźnik do kopii węzła arbitralnego, dokładnie to, co chcieliśmy.

Teraz przywróć oryginalną połączoną listę w jednym przebiegu i zwróć nową listę.

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

Rozwiązaniem jest pobierana z 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

Oto rozwiązanie rekurencji (w Javie):

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;  
    } 
} 

A oto rozwiązanie wykorzystujące HashMap (również w języku 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; 
    } 
} 

Drugie podejście nie tylko do odczytu wymogu jest możliwe here.

Answer 6

1. Rozpocznij od węzła głowy i utworzyć kopię węzła jeden po drugim
2. Podczas tworzenia kopii dokonać wpisu oryginalnego węzła i węzeł Kopiuj w hash mapie jako klucz, wartość.
3. utworzyć nową listę, gdy kopiujemy element jeden po drugim, otrzymujemy następną wartość wskaźnika dla każdego węzła. 4. następnie przejdź ponownie oryginalną listę z nową listą, aby skopiować losowy wskaźnik. możemy uzyskać losowy wskaźnik dla odpowiedniego węzła na mapie skrótu.

Szczegółowe wizyty wyjaśnienie: http://www.dscoding.com/2016/10/copy-linked-list-with-random-pointer.html