02-05-2012, 00:27
|
|
|
|
חבר מתאריך: 04.11.04
הודעות: 6,986
|
|
אפשר לעשות את זה ב-[tex]O(d)[/tex] בממוצע על הקלט עם hash-table, לא רואה איך אפשר לעשות את זה ב-[tex]O(d)[/tex] במקרה הגרוע.
קשה לי לתת רמז בלי לתת את הפיתרון המלא אז אני אתן פיתרון ב-[tex]O(d^2)[/tex] ותנסי לחשוב איך אפשר לשפר את זה:
*הקוד הזה בטח עם באגים, לא בדקתי אותו, אבל זה הרעיון הכללי.
קוד:
l* find_merge (l* l1,l* l2) {
int idx=0;
while(l1)
{
l* tmp2=l2;
for (int i=0 ; i<=idx ; ++i) {
if (l1 == tmp2)
return l1;
tmp2=tmp2->next;
}
l1=l1->next;
idx++;
}
}
|