6

次のランダムポインターを使用してリンクリストをコピーする必要があります。通常の次のポインターはリンクリストの次の要素を指し、ランダムポインターは他のノードまたはそれ自体を指す場合があります。特定のリストをいつでも変更することを許可されていない場合、これを行うにはどうすればよいですか。リストには読み取り権限のみが与えられます。

4

6 に答える 6

16

エレガントなソリューション (線形時間、一定空間):

ノード 1、2、3...n のコピーを作成し、1 と 2、2 と 3 などの間に挿入します。ここではrandomフィールドを無視します。したがって、リストには合計 2n 個のノードがあります。

random次の方法で、1 回のパスで新しいノードのフィールドの値を設定します。

original.next.random = original.random.next

LHS はrandom新しく作成されたノードのフィールドであり、RHS は任意のノードのコピーへのポインタであり、まさに私たちが望んでいたものであるため、これは機能します。

ここで、元のリンク リストを 1 回のパスで復元し、新しいリストを返します。

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

解決策はここから取られます。

于 2013-09-08T14:06:15.773 に答える
13

最も簡単な解決策は、次のようなものです...

next元のリンクされたリストをトラバースし、新しいリストの対応するノードを指す適切なポインターを使用して、元のリストと同じノードを持つ別のリンクされたリストを作成します。randomポインターは今のところそのままにしておきます。

リストをトラバースしている間に、古いリストのノード アドレス/ポインターと新しいリストのノード アドレス/ポインターをassociative array(AKA マップ、ハッシュ テーブルなど) に配置します。古いリストのノード アドレス/ポインターはkey、新しいリストのノード アドレス/ポインタはvalue.

次に、新しいリストをトラバースしrandom、すべてのノードのポインターを、ポインターに等しいにvalue対応する連想配列の に置き換えます。keyrandom

ハッシュ テーブルを連想配列として使用すると、元のリストの要素数に比例した時間とメモリ コストを実現できます。

このソリューションの時間と空間の複雑さはそれぞれ O(n) です。

于 2013-03-06T06:59:37.600 に答える
1 
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;
}
于 2013-03-30T20:46:22.923 に答える
0 
#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;    
}
于 2014-08-30T15:20:51.610 に答える