Weird List

[•Cosmin]

http://infoarena.ro/blog/weird-list

[•rgrig]

Poti sa aloci clona contiguu (cu malloc(sizeof(node)*size)) sau trebuie fiecare nod separat?

[•Cosmin]

Fiecare nod separat.

[•MciprianM]

Se poate sa existe doua noduri diferite care sa aiba cel de-al doilea pointer spre acelasi element?

[•Cosmin]

da

[•mihai_florea]

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:

Cod:

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.

[•Cosmin]

edit

Hmm, cred ca le incurci pe acolo. Verifica pe cateva exemple.

[•MciprianM]

Si eu cred ca am gasit solutia:

http://pastie.org/private/kyheitcuspp4bosfxhkq

[•Cosmin]

Da Ciprian, a ta e buna   Cred ca tre sa pun probleme mai grele .

[•skipy]

Se poate modifica lista originala?

[•wefgef]

Da.