Cloning a linked list where each node has a random pointer to any other node in linked list

Question

Please help me find what is wrong with my code (1).

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.

The task is to complete the function copyList() which takes one argument the head of the linked list to be cloned and should return the head of the cloned linked list. NOTE : If their is any node whose arbitrary pointer is not given then its by default null.

I tried to write code for the above problem..but it is not working

// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *next;
    Node *arb;

    Node(int x) {
        data = x;
        next = NULL;
        arb = NULL;
    }
};

void print(Node *root) {
    Node *temp = root;
    while (temp != NULL) {
        int k;
        if (temp->arb == NULL)
            k = -1;
        else
            k = temp->arb->data;
        cout << temp->data << " " << k << " ";
        temp = temp->next;
    }
}

Node *copyList(Node *head);

void append(Node **head_ref, Node **tail_ref, int new_data) {

    Node *new_node = new Node(new_data);
    if (*head_ref == NULL) {
        *head_ref = new_node;
    } else
        (*tail_ref)->next = new_node;
    *tail_ref = new_node;
}

bool validation(Node *head, Node *res, Node *cloned_addr,
                Node *generated_addr) {

    if (generated_addr == cloned_addr) return false;

    Node *temp1 = head;
    Node *temp2 = res;

    int len1 = 0, len2 = 0;
    while (temp1 != NULL) {
        len1++;
        temp1 = temp1->next;
    }
    while (temp2 != NULL) {
        len2++;
        temp2 = temp2->next;
    }

    /*if lengths not equal */

    if (len1 != len2) return false;

    temp1 = head;
    temp2 = res;
    while (temp1 != NULL) {
        if (temp1->data != temp2->data) return false;
        if (temp1->arb != NULL and temp2->arb != NULL) {
            if (temp1->arb->data != temp2->arb->data) return false;
        } else if (temp1->arb != NULL and temp2->arb == NULL)
            return false;
          else if (temp1->arb == NULL and temp2->arb != NULL)
            return false;
        temp1 = temp1->next;
        temp2 = temp2->next;
    }
    return true;
}

/* Driver program to test above function*/
int main() {
    int T, i, n, l, k;
    Node *generated_addr = NULL;
    /*reading input stuff*/
    cin >> T;

    while (T--) {
        generated_addr = NULL;
        struct Node *head = NULL, *tail = NULL;

        cin >> n >> k;
        for (i = 1; i <= n; i++) {
            cin >> l;
            append(&head, &tail, l);
        }

        for (int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;

            Node *tempA = head;
            int count = -1;

            while (tempA != NULL) {
                count++;
                if (count == a - 1) break;
                tempA = tempA->next;
            }
            Node *tempB = head;
            count = -1;

            while (tempB != NULL) {
                count++;
                if (count == b - 1) break;
                tempB = tempB->next;
            }

            // when both a is greater than N
            if (a <= n) tempA->arb = tempB;
        }
        /*read finished*/

        generated_addr = head;
        Node *res = copyList(head);

        Node *cloned_addr = res;

        cout << validation(head, res, cloned_addr, generated_addr) << endl;
    }

    return 0;
}
// } Driver Code Ends


/*  the node structure is as follows

struct Node {
    int data;
    Node *next;
    Node *arb;

    Node(int x) {
        data = x;
        next = NULL;
        arb = NULL;
    }
};
*/

// Should return the head of the copied linked list the
// output will be 1 if successfully copied
Node *copyList(Node *head) {
    if(!head)
    return nullptr;
    
    Node*q=head;
    Node*clone=new Node(q->data);
    clone->next=0;
    clone->arb=q->arb;
    Node*p=clone;
    Node*r=q;
    q=q->next;
    while(q)
    {
        r->next=p;
        p->next=new Node(q->data);
        p=p->next;
        p->next=0;
        p->arb=q->arb;
        r=q;
        q=q->next;
    }
    r->next=p;
    p=clone;
    while(p)
    {
        if(p->arb)
        p->arb=p->arb->next;
        p=p->next;
    }
    
    return clone;

    
}

When I had such task in a real world problem, I used a std::map<Node*, Node*>. In the first iteration, I cloned the nodes: For each original node, create a copy but store the original pointer in Node::arb. (I would call this a flat copy.) Additionally, the map is filled with original nodes as key and new nodes (the copy) as values. In a second iteration, the Node::arbs of the copied nodes are replaced using the map for look-up. (If Node::arb points to something which is not found in the map then fall back to default null.) — Scheff's Cat
For reference, the problem is located at leetcode.com/problems/copy-list-with-random-pointer/description. There's a lot of code here--more than is necessary to complete the task. I recommend re-strategizing and I second the suggestion to use a hash map if you're allowed extra space. — ggorlen
If you want to challenge yourself, try to do it with no containers (e.g. map<...>), no structs or classes except Node exactly as defined above, and in O(n). — Beta

Miguel Miguel · Accepted Answer · 2020-08-14T23:30:50

The pointers inside the list cannot be assigned until you have constructed the cloned list itself, because until then the nodes to point will not exist.

Therefore, you need two iterations: the first one to clone the list and make a dictionary that associates the original node with the clone, and the second one to update the pointers. The code would look like this:

Node *copyList(Node *head) {
    if(!head)
    return nullptr;
    
    Node* it1 = head;
    Node* clone = new Node;
    Node* it2 = clone;
    
    std::map<Node*, Node*> nodeDict;
    nodeDict[nullptr] = nullptr;
    
    // first iteration: create the list and the values
    while(it1){
        it2->data = it1->data;
        nodeDict[it1] = it2;
        
        it1 = it1->next;
        it2->next = it1 ? new Node: nullptr;
        it2 = it2->next;
    }
    // second iteration: connect the nodes
    it1 = head;
    it2 = clone;
    while(it1){
        it2->arb = nodeDict[it1->arb];
        it1 = it1->next;
        it2 = it2->next;
    }
    
    return clone;
}

Cloning a linked list where each node has a random pointer to any other node in linked list

1 Answers