6

我需要复制带有下一个和随机指针的链表。下​​一个指针通常指向链表中的下一个元素，随机指针可能指向任何其他节点，甚至指向自身。如果我在任何时候都不允许修改给定的列表，怎么办？列表上只有读取权限。

4

6 回答 6

16

优雅的解决方案（线性时间，恒定空间）：

创建节点 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;

解决方案取自这里。

于 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 回答
0

这是递归解决方案（在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;  
    }  
}

没有只读要求的另一种方法在这里是可能的。

于 2015-07-03T23:20:48.567 回答
0
  1. 从头节点开始，一个一个地创建Node的副本
  2. 当您创建副本时，将哈希图中的原始节点和复制节点作为键、值。
  3. 当我们逐个复制元素时创建一个新列表，因此我们为每个节点获得了一个下一个指针值。4.然后用新列表再次遍历原始列表以复制随机指针。我们可以得到哈希图中各个节点的随机指针。

详细解释请访问：http ://www.dscoding.com/2016/10/copy-linked-list-with-random-pointer.html

于 2016-11-15T09:32:43.537 回答