فرض کنید که داده‌ساختار لینک لیست ‎‎ دوطرفه از عناصری با ‎type‎ زیر ساخته شده است:

‎struct Node{‎
    ‎Node *next‎, ‎*prev;‎
    ‎int key;‎
‎};‎

‎ فرض کنید که ‎next‎ آخرین عنصر لینک لیست و ‎prev‎ اولین عنصر لینک لیست ‎NULL‎ است. شما بایستی تابع ‎Node * insertLinkedList(Node *start1‎, ‎Node *start2‎, ‎Node *p‎, ‎int where)‎ را پیاده سازی کنید. start1‎ و ‎start2‎ به ابتدای دو لینک لیست مختلف اشاره می‌کنند. این تابع باید لینک لیستی که ‎start2‎ به آن اشاره می‌کند را در لینک لیستی که ‎start1‎ به ابتدای آن اشاره می‌کند وارد کند و اشاره‌گر به ابتدای لینک لیست حاصل را بعنوان خروجی برگرداند. p‎ یکی از عناصر لینک لیستی است که ‎start1‎ به آن اشاره می‌کند. در صورتی که ‎where=0‎ باشد، لینک لیست دوم بایستی قبل از عنصر ‎p‎ وارد شود و اگر ‎where=1‎ باشد، لینک لیست دوم باید بعد از عنصر ‎p‎ وارد شود. ‎ دقت کنید شما باید این تابع را در ‎${\cal O}(1)$‎ پیاده سازی کنید.

بعنوان مثال اگر لینک لیست اوّل (از راست به چپ) شامل عناصر ‎۱‎ و ‎۲‎ و ‎۳‎ و ‎۴‎ باشد و ‎p‎ به عنصر اوّل (یعنی ‎۱) اشاره کند و لینک لیست دوم شامل عناصر ۵‎ و ‎۶‎ و ‎۷‎ و ‎۸‎ باشد، اگر ‎insertLinkedList(start1‎, ‎start2‎, ‎p‎, ‎0)‎ را اجرا کنیم لینک لیست اول به صورت ‎۵‎ و ‎۶‎ و ‎۷‎ و ‎۸‎ و ‎۱‎ و ‎۲‎ و ‎۳‎ و ‎۴‎ در می‌آید ولی اگر ‎insertLinkedList(start1‎, ‎start2‎, ‎p‎, ‎1)‎ را اجرا کنیم لینک لیست اول به صورت ‎۱‎ و ‎۵‎ و ‎۶‎ و ‎۷‎ و ‎۸‎ و ‎۲‎ و ۳‎ و ‎۴‎ در می‌آید.‎

• سوال بعد
• سوال قبل