====== سوال ۹ ======


فرض کنید که داده‌ساختار لینک لیست ‎‎ دوطرفه از عناصری با ‎type‎ زیر ساخته شده است:
<code c>
‎struct Node{‎
    ‎Node *next‎, ‎*prev;‎
    ‎int key;‎
‎};‎
</code> 
‎
فرض کنید که ''‎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)''‎ را اجرا کنیم لینک لیست اول به صورت ‎۱‎ و ‎۵‎ و ‎۶‎ و ‎۷‎ و ‎۸‎ و ‎۲‎ و ۳‎ و ‎۴‎ در می‌آید.‎

  * [[سوال ۱۰|سوال بعد]]
  * [[سوال ۸|سوال قبل]]