copy a linked list with next and random pointer, only read privileges are given on list

clone a linked list with next and random pointer
clone a linked list with next and random pointer in o(1) space
copy linked list in c
copy linked list python
copy list interviewbit
copy one linked list into another in c
python linked list random pointer
copy linked list with arbitrary pointer leetcode

I need to copy a linked list with next and random pointer.The next pointer as usual points to the next element in the linked list and the random pointer might point to any of the other node or even on itself. How can this be done if I am not allowed to modify the given list at any time, only read privileges are given on the list.

Elegant solution (linear time, constant space):

Create copies of Node 1, 2, 3...n and insert them between 1 and 2, 2 and 3 and so on, ignoring the random field for now. So there are 2n nodes total in the list.

Now set the value of random fields in the new nodes in the following way with a single pass:

original.next.random = original.random.next

This works, because LHS is the random field in the newly created node, and RHS is the pointer to the arbitrary's node's copy, exactly what we wanted.

Now restore the original linked list in a single pass, and return the new list.

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

The solution is taken from here.

Clone a linked list with next and random pointer, Select a Random Node from a Singly Linked List · Given only a pointer/reference to a node to be deleted in a singly linked list, how do you delete it? Point arbit  1) Create all nodes in copy linked list using next pointers. 2) Store the node and its next pointer mappings of original linked list. 3) Change next pointer of all nodes in original linked list to point to the corresponding node in copy linked list. Following diagram shows status of both Linked Lists after above 3 steps.

The simplest solution would be something like this...

You traverse the original linked list and create another linked list, whose nodes are the same as in the original list, with proper next pointers, pointing to the corresponding nodes of the new list. You keep the random pointers as they are for now.

While you're traversing the list you also put the old list's node address/pointer and the new list's node address/pointer onto an associative array (AKA map, hash table, etc), where the old list's node address/pointer is the key and the new list's node address/pointer is the value.

Then you traverse the new list and replace the random pointer in every node with the value from the associative array corresponding to the key equal to the random pointer.

A hash table can be used as an associative array to achieve time and memory cost proportional to the number of elements in the original list.

The time & space complexity of this solution is O(n) each.

Clone a linked list with next and random pointer in O(1) space , Select a Random Node from a Singly Linked List · Given only a pointer/reference to a node to be deleted in a singly linked list, how do you delete it? Point arbit  Clone a linked list with next and random pointer in O(1) space Given a linked list having two pointers in each node. The first one points to the next node of the list, however, the other pointer is random and can point to any node of the list.

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

Copy List with Random Pointer, Given a doubly linked list, in which one pointer is pointing to the next node just like in a singly linked list. The second pointer however can point to any node in  A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where: val: an integer representing Node.val; random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node. Example 1:

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

Clone a Linked List with next and random pointer, A linked list is given such that each node contains an additional random pointer which copy.next = p.next; p.next = copy; p = copy.next; } // copy random pointer for each If you want someone to read your code, please put the code inside  Copy a linked list with next and arbit pointer July 15, 2013 10:07 pm | Leave a Comment | crazyadmin Problem : Given a doubly linked list with one pointer of each node pointing to the next node just like in a singly linked list.

Here is the recursion solution (in 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;      
    }  
}  

And here is the solution using HashMap (also in 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;  
    }  
} 

The other approach without read-only requirement is possible here.

LeetCode – Copy List with Random Pointer, The next technological frontier will be our own bodies. Genetics, materials science, tissue engineering and nanotechnology are already yielding products to help  Given a linked list with random pointers. Give steps to Clone/copy the linked list. Clone/Copy a linked list with next and random pointers a suggested video will automatically play next.

Popular Science, Please sign this permission form: I authorize my midterm grade to be posted (on the Circular Linked List: Nodes in a linked list are linked together using a next field, P . The head is where to add/write next, the tail is where to delete/read next. Explain how to implement doubly linked lists using only one pointer value x . Copy List: A linked list is given such that each node contains an additional random pointer which could point to any node in the list or NULL. Return a deep copy of the list. Example Given list 1 -> 2 -> 3 with random pointers going from 1 -> 3 2 -> 1 3 -> 1 You should return a deep copy of the list.

Stack using circular linked list, A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image: In simple words, a linked list consists of nodes where each node contains a data field and a reference (link) to the next node in the list.

Clone A Linked List (With Random Pointers), You are given a Singly Linked List with N nodes where each node next pointing to its next node. You are also given M random pointers , where you will be given M number of pairs denoting two nodes a and b i.e. a->arb = b. Input: First line of input contains number of testcases T. For each testcase, first line of input contains two integers N and M.

Comments
  • Either I am missing something, or your description of the problem is missing something. Surely if you have read access to the original list and next pointers, you just start at the list head, copy that node and follow the next pointer - done?
  • @us2012 I think you are expected to properly initialize those "random" pointers so they point to the nodes of the new list and not the nodes of the original list. So, it's not a full node copy, you need to change two pointers in every node.
  • @Alexey Ah! Yeah, that makes more sense.
  • the solution requires O(n) solution where n is the no of nodes in the list.
  • the pointers both the next and the random pointer can't be changed in the original list
  • What about the restriction that the original list be read-only?
  • Yep, nice. Would be interesting to see whether there is a solution where the O(n) is strict rather than amortized!
  • +1 . Once in an interview with microsoft i gave the same answer as that of @Max (inserting nodes between the old nodes then ....... ). But they explicitly asked me to solve the question using HashMap. Exact solution given by Alexey Frunze was expected. Somehow i arrived to the same answer.
  • welcome to Stack Overflow. you may want to add some explanations as to why and how your answer works. (be it in text or code comments). so the OP can learn from it.
  • This code is quite involved and having no commentary with this code is not justified. Please leave some comments or explanation as to how this code works, and how you justified the design choices you made to do this.