Parcurgem lista de 2 ori. Prima data pentru fiecare nod original, cream un nou nod si pentru acesta setam pointarul random spre pointerul random original din lista data, iar pointerul random al nodului original il setam catre nodul nou creat. La a 2-a parcurgere "corectam" legaturile.
Niste "pseudocod" ca sa fie mai clar:
x = first;
prev = null;
while (x != null) {
y = new Node();
if (prev != null) prev->next = y;
y->rnd = x -> rnd;
x->rnd = y;
x = x->next;
prev = y;
}
for (x = first; x != NULL; x=x->next) {
y = x->rnd;
x->rnd = y->rnd;
y->rnd = y->rnd->rnd;
}
Dap nu merge in caz ca exista legaturi random inapoi in lista.