Linked ListListNode · head · traversal · dummy node · reverse · fast & slow
الـ array بتحط العناصر جنب بعض في الـ memory. الـ linked list بتفرّقهم في أي حتة، وكل عنصر ماسك عنوان اللي بعده. الفكرة البسيطة دي بتخلّي الـ insert والـ delete O(1)، وبتفتح باب مسائل كلها لعب بالأسهم: reverse، و merge، ودواير.
هتطلع من الفصل ده وإنت عارف
- يعني إيه node و reference، وليه الـ linked list بطيئة في الـ access وسريعة في الـ insert والـ delete.
- تمشي على list وتعدّل فيها من غير ما تقطعها، ومن غير ما تقرا
.nextمنnull. - تستخدم الـ dummy node عشان تشيل الـ special cases بتاعة الـ head من الكود خالص.
- تعمل reverse لـ list بـ
prevوcurوnext، وإنت فاهم كل سهم بيتقلب إمتى وليه. - تحل Merge Two Sorted Lists و Remove Nth From End و Linked List Cycle I و II و Reorder List، وتعرف تثبت ليه رجوع pointer للـ head بيلاقي بداية الدايرة.
ليه Linked List؟
في الفصل اللي فات عملنا queue بـ linked list عشان نهرب من shift() اللي بتزق كل العناصر. استخدمنا الـ nodes هناك من غير ما نقف عندها. دلوقتي هنقف عندها ونفهمها from scratch، لأن نص مسائل الانترفيو على الـ lists عبارة عن لعب بالأسهم دي.
افتكر الـ array: العناصر قاعدة جنب بعض في الـ memory. عشان كده arr[i] سريعة: الجهاز بيحسب العنوان بعملية جمع واحدة. بس التمن إن الـ array لازم تفضل متصلة، فلو عايز تحط عنصر في أولها لازم تزق الباقي. الـ linked list بتحل ده بطريقة تانية خالص: كل عنصر في أي حتة، وكل عنصر بيقولك اللي بعده فين. بص على الفرق في الـ memory نفسها:
head هو أول ورقة في إيدك، وكل node فيها قيمة ومكان اللي بعدها، وآخر node فيها null. وعشان توصل للورقة الخامسة لازم تعدّي على الأربعة اللي قبلها، no shortcuts.
طب كسبنا إيه في المقابل؟ خد أبسط مثال: insert في أول الـ array، و insert في أول الـ list:
الـ array عملت نقلة لكل عنصر، يعني O(n). الـ list عملت خطوتين مهما كان طولها، يعني O(1). ده الـ trade-off كله في جملة: الـ array سريعة في الـ access، والـ list سريعة في التعديل لو إنت واقف في المكان.
في الانترفيو نادرًا ما هتختار linked list بنفسك. LeetCode بيبعتلك head جاهز، والمطلوب تغيّر الأسهم صح: من غير ما تضيّع جزء من الـ list، ومن غير ما تقرا .next من null.
طب إزاي تعرف أنهي حيلة من حيل الـ linked list المسألة عايزاها؟ ده الجزء الجاي.
إزاي تعرفه من المسألة
المسألة نفسها بتقولك «given the head of a linked list»، فمش محتاج تخمّن الـ data structure. السؤال الحقيقي: أنهي حيلة؟ الكلمات دي بتوجّهك:
لو المسألة محتاجة random access أو binary search، الـ list هتبقى بطيئة لأن الوصول للنص لوحده O(n). ساعتها حوّلها لـ array الأول.
| الموقف | الحيلة | أشهر مسائل |
|---|---|---|
| تمشي على كل node، تعدّ، تدوّر | cur واحد بيمشي لحد null | Remove Duplicates from Sorted List |
| الـ head ممكن يتمسح أو يتغيّر، أو بتبني list جديدة | dummy node قبل الـ head | Remove Elements، Merge Two Lists، Remove Nth، Add Two Numbers |
| الترتيب لازم يتعكس | prev و cur و next | Reverse List، Reverse List II، Palindrome List |
| النص، أو فيه دايرة | fast & slow | Middle، Cycle I و II |
| الـ node رقم k من الآخر | اتنين pointers بينهم gap ثابت | Remove Nth From End |
| مسألة كبيرة | تركيبة: middle + reverse + merge | Reorder List، Palindrome List |
flowchart TD
A["Linked list problem"] --> B{"Can the head change, or are you building a new list?"}
B -- yes --> D["Start with a dummy node"]
B -- no --> C{"Need the middle, a cycle, or the k-th from the end?"}
D --> C
C -- yes --> F["Two pointers: fast and slow, or a fixed gap"]
C -- no --> E{"Does the order need to flip?"}
E -- yes --> R["Reverse with prev, cur, next"]
E -- no --> T["Plain walk with cur"]
الأسئلة دي مش بتستبعد بعض. Reorder List مثلًا بتعدّي على التلاتة.
قبل أي حيلة، لازم نعرف الـ node نفسها شكلها إيه في JS، ويعني إيه «pointer» في لغة ما فيهاش pointers.
الـ node و class ListNode
الـ node علبة فيها حاجتين بس: val القيمة، و next وده reference للـ node اللي بعدها. آخر node الـ next بتاعها null، يعني «مفيش حد بعدي».
في JS مفيش pointers زي C++، بس كل object بيتخزّن كـ reference. لما تكتب let cur = head إنت ما عملتش copy من الـ node، إنت عملت اسم تاني لنفس الـ node. فلما نقول «pointer» هنا، نقصد متغير شايل reference لـ node:
الـ key insight في الفصل كله: q = q.next بيحرّك الاسم بس ومش بيلمس الـ list. لكن q.next = something بيغيّر السهم اللي جوه الـ node، وده بيغيّر الـ list نفسها. أي سطر فيه .next = على الشمال بيعدّل الـ list، وأي حاجة تانية مجرد حركة أسامي.
- نفس التعريف اللي LeetCode بيكتبهولك في كومنت فوق الحل. في الاختبار مش هتكتبه، بس هتحتاجه وإنت بتجرّب على جهازك.
- الـ defaults بتخلّي
new ListNode(5)node لوحدها، وnew ListNode()تنفع dummy. وليهnullمشundefined؟ لأن شروطك كلهاcur !== null، وundefined !== nullبتطلع true، فهتكمّل وتضرب TypeError. - ده كل اللي جوه الـ node. هي مش عارفة مين قبلها، ولا الـ list طولها كام.
- تلات nodes منفصلين، كل واحدة الـ next بتاعها
null. لسه مفيش list. - هنا بنربط: «السهم اللي جوه a يشاور على b». الترتيب هنا مش فارق، بس في الـ insert والـ reverse هيبقى كل حاجة.
- مفيش object اسمه List. الـ list = reference لأول node. ضيّعت الـ head يبقى ضيّعت الـ list، ومفيش
.length: عايز الطول؟ امشي وعدّ.
| العملية | Array | Linked List | ليه |
|---|---|---|---|
| الوصول للعنصر رقم i | O(1) | O(n) | الـ list لازم تمشي من الـ head |
| insert أو delete في الأول | O(n) | O(1) | الـ array بتزق، الـ list بتغيّر سهم |
| insert أو delete بعد node معاك reference ليها | O(n) | O(1) | سهم أو اتنين |
| إضافة في الآخر | O(1) | O(n) أو O(1) | O(1) بس لو شايل reference لآخر node (tail) |
| البحث عن قيمة | O(n) | O(n) | الاتنين بيدوّروا عنصر عنصر |
| الـ memory | العناصر بس | العناصر + reference لكل node | كل node شايلة next زيادة |
prev كمان، فتمشي في الاتجاهين وتمسح node لوحدها من غير ما تدوّر على اللي قبلها. هتقابلها في LRU Cache (doubly linked list + hash map). أغلب مسائل LeetCode singly: next بس، وده موضوع الفصل.
عندنا list. أول حاجة هنعملها عليها: نمشي عليها من أولها لآخرها من غير ما نوقع في null.
المشي على الـ list (traversal)
أهم 4 سطور في الفصل. أي عدّ أو جمع أو بحث على list بيبدأ بيهم. هنكتبهم كـ toArray لأننا هنحتاجها بعدين عشان نجرّب حلولنا:
- ليه
curوما نمشيش بالـheadنفسه؟ لو حرّكتhead، بعد الـ loop هيبقىnullوضيّعت أول الـ list. خليها عادة: الـ head ثابت، وcurهو اللي بيمشي. - ليه
cur !== nullمشcur.next !== null؟ التاني بيقف على آخر node من غير ما يعالجها (هتطلّع[5, 1, 8]بس)، وعلى list فاضية بيضرب TypeError. الأول بيشتغل حتى لوhead === null: الـ loop مش هتدخل والإجابة[]. - ده مكان الشغل: هنا push، وفي مسائل تانية عدّ أو مقارنة.
- ده الـ
i++بتاع الـ linked list. نسيته؟ infinite loop. - كل node اتزارت مرة واحدة، فالوقت O(n).
x.next أو x.val، اسأل نفسك: «x ممكن يبقى null هنا؟». لو آه، لازم شرط قبله يحميه. أغلب الـ Runtime Errors في مسائل الـ list سببها سطر نسي السؤال ده.
ونفس الـ loop ممكن تتكتب for: for (let cur = head; cur !== null; cur = cur.next) { … }. نفس التلات أجزاء: بداية، شرط، خطوة.
المشي سهل. طب لو عايز تحط node جديدة في النص، أو تشيل واحدة؟
insert و delete لما يبقى معاك الـ node اللي قبل
في الـ array، الـ insert في النص بيزق. في الـ list بتغيّر سهمين بس. الشرط الوحيد: لازم يكون معاك الـ node اللي قبل المكان (prev). ليه؟ لأن السهم اللي هيتغيّر هو سهم اللي قبل، والـ list one-way: من node تقدر تروح لقدّام بس.
- node لوحدها، الـ next بتاعها
null. مكانها في الـ memory مش مهم. - ده لازم الأول. الـ node الجديدة تمسك باقي الـ list وهو لسه متاح في
prev.next. لو بدّلت السطرين،prev.nextهيبقى الـ node نفسها، فـnode.next = prev.nextهيخليها تشاور على نفسها: cycle، والـ list اتقطعت. - دلوقتي بس نحوّل سهم
prev. الـ rule: امسك اللي قدّام قبل ما تسيب. - guard: لو
prevآخر node، مفيش حاجة نمسحها، ومن غيرهprev.next.nextهيضرب TypeError. - الـ node المحذوفة مفيش حد بيشاور عليها، فالـ garbage collector هيشيلها. (في C++ كنت هتعمل
deleteبإيدك.) العمليتين O(1)، بس الوصول لـprevنفسه ممكن ياخد O(n).
طب لو عايز تمسح الـ head نفسه؟ مفيش node قبله. يا تكتب special case (head = head.next)، يا تستخدم الحيلة اللي جاية.
إزاي نخلّي الـ head ليه «prev» زي أي node تانية، فالـ special case يختفي؟
الـ dummy node: node مزيّفة بتشيل الـ special cases
المسألة: امسح كل الـ nodes اللي قيمتها val (LeetCode 203). الـ delete محتاج prev، والـ head مالوش prev. من غير حيلة، الكود بيبقى كده:
شغال، بس فيه loop مخصوصة للـ head وشرط زيادة cur !== null لأن الـ head ممكن يبقى null بعدها. كل special case زي ده فرصة bug وإنت متوتر في الاختبار.
dummy.next هو أول حباية.
- قيمته مش مهمة، عمرنا ما هنقراها. المهم إنه بيشاور على الـ head، فالـ head بقى ليه prev.
curبيبدأ من الـ dummy مش الـ head، لأننا دايمًا واقفين قبل الـ candidate. كده أول candidate هو الـ head نفسه.cur.next !== nullعشان محتاجين candidate. وcurنفسه عمره ما بيبقىnull: بيبدأ من dummy، وبيتحرك بس لـ node اتشيكنا إنها مش null.- ليه ما بنحرّكش
curبعد الـ delete؟ لأنcur.nextالجديد candidate جديد لسه ما اتشيكش. في6 → 6لو اتحركت هتعدّي التانية من غير ما تمسحها. - بنتحرك بس لما الـ node تفضل.
dummy.nextمشhead: المتغيرheadلسه بيشاور على أول node الأصلية، وممكن تكون اتمسحت.
const dummy = new ListNode(0) واختم بـ return dummy.next.
أول استخدام عملي للـ dummy: نبني list من array عشان نجرّب حلولنا على جهازنا.
تبني list من array عشان تجرّب
على LeetCode الـ judge بيبني الـ list من [1,2,3] ويبعتلك الـ head. على جهازك إنت اللي هتعمل ده، ونفس حيلة الـ dummy بتخلّي الكود 6 سطور:
- من غيره، أول append special case:
if (head === null) head = node; else tail.next = node;. tail= آخر node لحد دلوقتي. من غيره كل append هيمشي من الـ head للآخر، يعني O(n) لكل عنصر و O(n²) للكل.- نعلّق الجديدة ونقدّم الـ tail عليها. نفس ترتيب «امسك وبعدين اتحرك».
- لو
arrفاضية،dummy.nextلسهnull، وده بالظبط الـ list الفاضية. مفيشif.
وده الـ setup اللي هتجرّب بيه كل حل في الفصل. للمسائل اللي فيها cycle، LeetCode بيديك pos = الـ index اللي آخر node بترجعله (-1 يعني مفيش). الـ pos ده بيتستخدم في بناء الـ input بس، دالتك مش بتاخده:
فاضل أداة واحدة قبل المسائل: إزاي توصل لنص الـ list في لفة واحدة، وإنت مش عارف طولها؟
القالب: fast & slow ونص الـ list
شفناه في Two Pointers: slow بيمشي one step و fast بيمشي two steps. لما fast يخلص، slow يبقى قطع نص المسافة. هنا هنقف عند تفصيلة بتفرق في المسائل: لو الطول زوجي فيه نصّين، تاخد أنهي واحد؟
- ليه شرطين؟ fast هيعمل
fast.next.next، فلازمfastوfast.nextالاتنين موجودين. والترتيب مهم: الـ&&بيعمل short-circuit، فلوfast === nullالجزء التاني مش بيتحسب أصلًا. اقلبهم وهتضرب TypeError. - slow خطوة و fast خطوتين، فـ fast دايمًا قاطع ضعف slow.
- طول فردي: النص بالظبط. طول زوجي: النص التاني (4 في
1..6). - بيبص خطوة لقدّام زيادة، فبيقف بدري بخطوة. طول زوجي: النص الأول (3 في
1..6). خلي بالك:fast.nextعلىhead = nullهيضرب error، فاللي بينادي لازم يتشيك على الـ list الفاضية الأول. - ده آخر node في النص الأول، و
slow.nextأول النص التاني. ده اللي هنحتاجه في Reorder و Palindrome عشان نقسم الـ list.
| الـ list | A: middleNode | B: endOfFirstHalf |
|---|---|---|
| 1 → 2 → 3 → 4 → 5 | 3 | 3 |
| 1 → 2 → 3 → 4 → 5 → 6 | 4 | 3 |
| 1 → 2 | 2 | 1 |
| 1 | 1 | 1 |
كده الأدوات كلها معانا. نبدأ المسائل بأشهر واحدة فيهم، واللي كل الباقي مبني عليها: reverse.
مثال محلول 1: Reverse Linked List
معاك الـ head بتاع linked list. اقلب اتجاه كل الأسهم، ورجّع الـ head الجديد.
نفكّر فيها مع بعض
- افهم المطلوب: مش هنعمل list جديدة، هنقلب الأسهم نفسها. كل node كانت بتشاور على اللي بعدها، هتشاور على اللي قبلها، وأول node هتبقى آخر واحدة فالـ next بتاعها
null. - Brute force: نحط القيم في array، ونمشي تاني نكتبها بالعكس. O(n) وقت بس O(n) memory، وبيغيّر القيم مش الـ nodes.
- الـ key insight: نمشي مرة واحدة ونقلب سهم كل node. بس الـ list one-way، فمحتاجين نفتكر اللي قبل (
prev). ولما نقلب سهمcurهنضيّع الطريق لباقي الـ list، فلازم نحفظه فيnextقبل ما نقلب. - الخطة: 3 pointers و 4 سطور بترتيب ثابت في كل لفة: احفظ، اقلب، قدّم prev، قدّم cur.
- Edge cases: list فاضية ترجع
null، و node واحدة ترجع نفسها.
- ليه
null؟ أول node هتبقى الأخيرة، والأخيرة الـ next بتاعها لازمnull. لو بدأتprev = head، أول node هتشاور على نفسها. cur !== nullعشان نقلب كل node بما فيها الأخيرة. ولو الـ list فاضية الـ loop مش هتدخل ونرجّعnullصح.- الـ reference الوحيد لباقي الـ list هو
cur.next، والسطر الجاي هيكتب فوقه. احفظه الأول. - ده السطر الوحيد اللي بيغيّر الـ list فعلًا. الباقي كله حركة أسامي.
- الترتيب مهم:
prev = curقبلcur = next، وإلا prev هياخد قيمة next. وcur = nextمشcur.next، لأنcur.nextدلوقتي بيشاور لورا. - بعد الـ loop
curبقىnull، وprevواقف على آخر node الأصلية، وهي الـ head الجديد. مشhead: ده بقى آخر واحدة.
ده أهم animation في الفصل. كل سطر خطوة، وكل pointer move لوحده. بص على السهم الأصفر وهو بيتقلب:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| null | null | الـ loop مش بتدخل، و prev لسه null |
| 5 | 5 | لفة واحدة: 5.next = null وترجع 5 |
| 7 -> 9 | 9 -> 7 | أصغر list فيها سهم يتقلب فعلًا |
التعقيد: كل node بتتزار مرة، يعني O(n) وقت و O(1) memory (3 متغيرات بس).
النسخة الـ recursive
نفس المسألة ليها حل recursive قصير. هنا الكود والفكرة، والـ call stack متحرّك خطوة بخطوة في فصل الـ Recursion:
- الـ base case: list فاضية أو node واحدة معكوسة أصلًا.
- ثق إن النداء ده عكس كل اللي بعد
head.head.nextلسه بيشاور على نفس الـ node، وهي بقت آخر الجزء المعكوس. - خلّي الـ node دي تشاور لورا على
head. - وقطّع السهم القديم، وإلا الاتنين هيشاوروا على بعض: cycle.
- الـ head الجديد (آخر node أصلية) بيرجع زي ما هو من كل مستوى.
الـ reverse بيعدّل list واحدة. طب لو عندك اتنين وعايز تعمل منهم list جديدة؟
مثال محلول 2: Merge Two Sorted Lists
الجديد هنا إننا بنبني list جديدة من nodes جاية من اتنين lists، فهنستخدم الـ dummy مع pointer اسمه tail، زي buildList بالظبط.
عندك list1 و list2، كل واحدة مترتبة تصاعدي. ادمجهم في list واحدة مترتبة باستخدام نفس الـ nodes (من غير ما تعمل nodes جديدة)، ورجّع الـ head.
نفكّر فيها مع بعض
- Brute force: نجمع كل القيم في array، نعمل sort، ونبني list جديدة.
O((n+m) log(n+m))، وبيعمل nodes جديدة والمسألة عايزة نفس الـ nodes. - الـ key insight: أصغر عنصر فاضل لازم يكون واحد من الـ two heads. فنقارن الاتنين، وناخد الأصغر، ونقدّم في الـ list بتاعته بس. ده نفس الـ merge step بتاع merge sort.
- مين الـ head بتاع النتيجة؟ مش عارفين قبل أول مقارنة، وده special case. فنبدأ بـ dummy، ونعلّق عليه بـ
tail. - لما list تخلص: الباقي من التانية مترتب ومربوط أصلًا، وكله أكبر من أو يساوي اللي أخدناه. نعلّقه كله في خطوة واحدة، من غير loop.
- Edge cases: واحدة أو الاتنين فاضيين، قيم متساوية، أطوال مختلفة.
- الـ dummy بيشيل سؤال «النتيجة فاضية ولا لأ؟». و
tail= آخر node في النتيجة. &&: بنقارن بس طول ما الاتنين فيهم nodes. أول ما واحدة تخلص، مفيش حاجة نقارنها.<=ولا<؟ الاتنين صح للقيم. الـ<=بياخد من list1 في التساوي، فبيحافظ على ترتيب المتساويين (stable)، وده بيفرق لما الـ nodes شايلة data تانية.- بنعلّق الـ node نفسها (من غير copy) ونقدّم list1. السهم القديم بتاعها لسه بيشاور جوه list1، ومش مشكلة: هيتكتب فوقه في اللفة الجاية أو في سطر 14.
- برا الـ if/else لأنه مشترك في الفرعين.
- واحدة على الأقل خلصت. علّق الباقي من التانية كله مرة واحدة. ولو الاتنين
nullهيعلّقnull، وده صح. - الـ head الحقيقي، أيًّا كان جه من أنهي list.
في الـ animation، list1 باللون الأزرق و list2 بالأصفر، والأسهم الخضرا هي النتيجة وهي بتتبني:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| null, null | null | الـ loop مش بتدخل، و dummy.next = null |
| null, 0 | 0 | سطر 14 لوحده بيحلها |
| 2 -> 2, 2 | 2 -> 2 -> 2 | التساوي: <= بياخد من list1 الأول |
| 1 -> 2 -> 3, 7 -> 8 | 1 -> 2 -> 3 -> 7 -> 8 | list1 بتخلص كلها الأول، و list2 تتعلّق مرة واحدة |
التعقيد: كل لفة بتاخد node واحدة، يعني O(n + m) وقت، و O(1) memory. وفيه نسخة recursive قصيرة جدًا في فصل الـ Recursion، بس بـ O(n + m) stack.
لحد دلوقتي الـ pointers بيمشوا جنب بعض. طب لو عايز node بعدها بمسافة معينة من الآخر، وإنت مش عارف الطول؟
مثال محلول 3: Remove Nth Node From End
الجديد هنا: اتنين pointers بينهم gap ثابت، عشان نوصل لمكان من آخر الـ list في لفة واحدة. والـ dummy راجع تاني، لأن الـ node اللي هتتمسح ممكن تبقى الـ head.
امسح الـ node رقم n من آخر الـ list ورجّع الـ head. الـ n دايمًا valid: من 1 لحد الطول.
نفكّر فيها مع بعض
- افهم المطلوب: لو الطول
L، فرقمnمن الآخر هو رقمL - n + 1من الأول. وعشان نمسحه محتاجين اللي قبله. - حل بلفّتين: لفة تعدّ
L، ولفة تمشي من الـ dummyL - nخطوة. دهO(L)وحل كويس تمامًا. الـ follow-up بيطلب لفة واحدة. - الـ key insight: خلّي
fastيسبقslowبـnخطوة، وبعدين حرّكهم مع بعض. الـ gap ثابت، فلما fast يقف على آخر node، slow هيبقى قبل الـ target بالظبط. - ليه من الـ dummy؟ لو
n = Lالـ target هو الـ head، ومحتاجين node قبله. slow هيفضل واقف على الـ dummy. - Edge cases:
n = L(الـ head)،n = 1(آخر node)، list من node واحدة.
- الاتنين من الـ dummy، عشان لو الـ target هو الـ head، slow يبقى ليه مكان يقف فيه قبله.
i < nيعني n خطوة بالظبط. fast مش هيبقىnullهنا، لأنn ≤ Lو الـ dummy + L nodes.- الـ off-by-one كله هنا. فيه combo صح من اتنين: (gap = n ونقف لما
fast.next === null) أو (gap = n + 1 ونقف لماfast === null). لو خلطتهم، slow هيقف على الـ target مش قبله. - الاتنين خطوة، فالـ gap ثابت.
slow.nextهو الـ target، ومشnullلأن الـ gap ≥ 1. نطّ فوقه.- الـ head ممكن يكون هو اللي اتمسح، فـ
dummy.next.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| 3 -> 8 -> 1 -> 9 -> 4, n = 5 | 8 -> 1 -> 9 -> 4 | الـ head اتمسح: slow فضل على الـ dummy |
| 3 -> 8 -> 1 -> 9 -> 4, n = 1 | 3 -> 8 -> 1 -> 9 | آخر node: slow.next.next = null |
| 7, n = 1 | null | الـ list فضيت: dummy.next = null |
التعقيد: fast بيمشي الـ list مرة واحدة: O(L) وقت، لفة واحدة، و O(1) memory.
الـ gap كان ثابت. طب لو الاتنين بسرعات مختلفة، ممكن نكتشف إن الـ list ليها آخر أصلًا؟
مثال محلول 4: Linked List Cycle I و II
الجديد هنا: fast & slow مش بس بيلاقوا النص، بيكشفوا دايرة. وفي الجزء التاني فيه شوية رياضة بسيطة بتقولك الدايرة بتبدأ فين.
هل الـ list فيها دايرة؟ يعني لو فضلت تمشي بـ next، هترجع لـ node عدّيت عليها بدل ما توصل null؟
نفس الكلام، بس رجّع الـ node اللي الدايرة بتبدأ عندها، أو null لو مفيش. من غير ما تعدّل الـ list.
نفكّر فيها مع بعض
- Brute force:
Setفيه الـ nodes اللي زرناها. أول node تتكرر هي بداية الدايرة.O(n)وقت وO(n)memory. خلي بالك: بنخزّن الـ nodes نفسها مش القيم، لأن القيم ممكن تتكرر. - من غير memory: fast & slow. لو مفيش دايرة، fast هيوصل
null. لو فيه، الاتنين هيدخلوها، و fast بيقرّب من slow node واحدة كل خطوة، فلازم يحصّله. - ليه fast مش بينط فوق slow؟ المسافة بينهم جوه الدايرة بتقل 1 بالظبط كل خطوة (fast +2، slow +1)، فلازم توصل صفر.
- للـ 142: مكان المقابلة مش بالضرورة البداية. الرياضة تحت بتثبت: رجّع pointer للـ head، وحرّك الاتنين one step، هيتقابلوا عند البداية.
- الاتنين من الـ head. لو
head === nullالـ loop مش هتدخل والإجابة false. - نفس شرط middleNode: fast محتاج خطوتين متاحين.
- اتحرك الأول وبعدين قارن. في البداية الاتنين على الـ head، فلو قارنت قبل الحركة هترجع true على طول. و
===على objects بيقارن الـ reference: node تانية قيمتها 5 مش «نفس الـ node». - fast وصل
null، يبقى الـ list ليها آخر.
سمّي: a = عدد الخطوات من الـ head لبداية الدايرة، و c = طول الدايرة، و b = المسافة من بداية الدايرة لمكان المقابلة.
- slow مشي
a + b. (ما بيكمّلش لفة كاملة قبل المقابلة، لأن fast بيحصّله في أقل منcخطوة.) - fast مشي
a + b + k·c، يعني نفس المسافة +kلفات زيادة. - fast بيمشي ضعف slow:
a + b + k·c = 2(a + b)، فـa + b = k·c، فـa = (k − 1)·c + (c − b).
c − b هي المسافة من مكان المقابلة لحد بداية الدايرة. يعني لو p مشي a خطوة من الـ head، و slow مشي a خطوة من مكان المقابلة، slow هيمشي c − b يوصل البداية، وبعدين k − 1 لفة كاملة ترجّعه لنفس المكان. الاتنين بيوصلوا البداية في نفس اللحظة.
- phase 1 هي
hasCycleبالظبط. - pointer جديد من الـ head. ده الـ
aخطوة اللي في المعادلة. whileمشdo: لو الدايرة بادئة من الـ head (a = 0)، المقابلة بتكون عند الـ head، والـ loop مش هتدخل.- الاتنين one step. لو slow فضل بيمشي خطوتين، المعادلة تبوظ ومش هيتقابلوا عند البداية.
- البداية. ورجّعنا node، مش index ولا قيمة.
المثال: a = 2 (الـ 1 والـ 2 قبل الدايرة)، والدايرة 3 → 4 → 5 → 6 → 7 → 3 طولها c = 5. شوف الأرقام وهي بتطلع:
| Input | 141 | 142 | ليه الحالة دي مهمة |
|---|---|---|---|
| null | false | null | الـ loop مش بتدخل |
| 1 -> 2 -> 3 | false | null | fast بيوصل null |
| 1, 1.next = 1 | true | 1 | self-loop: a = 0 و c = 1 |
| 1 -> 2 -> 3, 3.next = 1 | true | 1 | الدايرة من الـ head: phase 2 بترجع على طول |
التعقيد: phase 1 أقل من a + c خطوة لـ slow، و phase 2 بالظبط a خطوة. يعني O(n) وقت و O(1) memory.
O(n) memory. لما يطلب O(1)، اكتب fast & slow. ولو سألك «ليه الرجوع للـ head بيشتغل؟»، اكتب المعادلة a = (k − 1)·c + (c − b) وارسم الدايرة.
شفنا الـ middle والـ reverse والـ merge كل واحد لوحده. آخر مثال بيستخدمهم التلاتة مع بعض.
مثال محلول 5: Reorder List
الجديد هنا مفيش حيلة جديدة. الجديد إنك تقسم مسألة medium لـ 3 أدوات عندك أصلًا: endOfFirstHalf، و reverseList، و merge بالتبادل.
عندك L0 → L1 → … → Ln. رتّبها تبقى L0 → Ln → L1 → Ln-1 → L2 → …: واحدة من الأول وواحدة من الآخر بالتبادل. عدّل الـ nodes نفسها مش القيم، والدالة مش بترجّع حاجة.
نفكّر فيها مع بعض
- Brute force: حط الـ nodes (الـ references) في array، واعمل two pointers من الطرفين وانت بتربط.
O(n)وقت وO(n)memory. إجابة أولى كويسة. - المشكلة: محتاجين ناخد من الآخر، والـ list one-way. بس لو عكسنا النص التاني،
Ln, Ln-1, …هتبقى بالترتيب العادي من الأول! - الخطة: (1) لاقي آخر النص الأول بـ
endOfFirstHalf. (2) اقطع الـ list، واعكس النص التاني. (3) ادمج بالتبادل: واحدة من هنا وواحدة من هنا. - ليه نقطع؟ لو ما عملناش
slow.next = null، آخر node في النص الأول هتفضل بتشاور جوه النص التاني، وبعد الدمج هيطلع cycle. - Edge cases: 0 أو 1 أو 2 nodes: مفيش حاجة تتغيّر، بس الكود لازم ما يضربش.
- 0 أو 1 node: مفيش حاجة تترتب. والأهم إن النسخة B بتقرا
fast.next، فلازم الـ head مشnull. - النسخة B من fast & slow: slow بيقف على آخر النص الأول، فالنص الأول ≥ التاني.
- نمسك أول النص التاني، وبعدين نقطع. نفس rule الـ insert: امسك قبل ما تسيب.
- ده
reverseListحرفيًا، بس علىsecond. بعدهاprev= آخر node أصلية. - ليه
second !== nullمشfirst؟ لأن النص التاني ≤ الأول. لما يخلص نقف، واللي فاضل من الأول (لو الطول فردي) في مكانه الصح ومربوط أصلًا. - احفظ الاتنين الأول. السطرين الجايين هيكتبوا فوق
first.nextوsecond.next. - دخّل
secondبينfirstواللي كان بعدها. - قدّم الاتنين للزوج الجاي.
الأزرق النص الأول، والأصفر النص التاني. خلي بالك من لحظة القطع:
التعقيد: 3 لفّات كل واحدة ≤ n، يعني O(n) وقت و O(1) memory.
في كل مثال كان فيه سطر واحد لو غلط بيبوّظ كل حاجة. يلا نجمع الغلطات دي في مكان واحد.
غلطات مشهورة
كل غلطة هنا سطر واحد، والنتيجة يا Wrong Answer، يا TypeError، يا TLE من loop ما بتخلصش.
1. قلبت السهم قبل ما تحفظ اللي بعده
الصح: const next = cur.next قبل أي cur.next =. الـ rule: امسك اللي قدّام قبل ما تسيب.
2. الترتيب الغلط في الـ insert
الصح: node.next = prev.next الأول، وبعدين prev.next = node.
3. قريت .next من null
الـ && بيقرا من الشمال لليمين ويقف عند أول false. حط الشرط اللي بيحمي (fast !== null) الأول. ونفس الكلام لـ while (cur.next !== null) على list ممكن تبقى فاضية.
4. رجّعت head بدل dummy.next
المتغير head عمره ما اتغيّر، فلسه بيشاور على أول 6، ومنها الأسهم القديمة لسه موجودة. الـ head الحقيقي دايمًا dummy.next.
5. قارنت بالقيمة بدل الـ node
6. نسيت تقطع الـ list في Reorder
آخر node في النص الأول لازم الـ next بتاعها يبقى null قبل الـ weave. ولو الـ judge حاول يطبع list فيها cycle، هتاخد TLE أو Memory Limit مش Wrong Answer، فالغلطة دي صعب تلاحظها.
دلوقتي جرّب نفسك: كام سؤال سريع، وتمرين تفكّر فيه قبل ما تفتح الحل.
اختبر نفسك
في reverseList، لو بدّلت prev = cur; و cur = next; (يعني cur = next الأول)، إيه اللي هيحصل مع 1 → 2 → 3؟
- نفس النتيجة، الترتيب مش فارق
- هيعكس نص الـ list بس
prevهياخد قيمةcurالجديدة، فالـ nodes هتشاور على نفسها والدالة هترجّعnull- TypeError على طول
بعد cur = next، السطر prev = cur بيخلّي prev = نفس الـ node اللي cur عليها. في اللفة الجاية cur.next = prev يعني cur.next = cur: self-loop. وفي الآخر cur و prev الاتنين null.
ليه removeElements بترجّع dummy.next مش head؟
- عشان
headبقىnullبعد الـ loop - عشان أول node أصلية ممكن تكون اتمسحت، والمتغير
headلسه بيشاور عليها - عشان الـ dummy أسرع
- مش فارقة، الاتنين واحد دايمًا
إحنا ما حرّكناش head خالص، فهو لسه على الـ node الأصلية. لو اتمسحت، الـ head الحقيقي الجديد مكتوب في dummy.next بس.
في Remove Nth، لو غيّرت شرط الـ while لـ fast !== null من غير ما تغيّر الـ gap (لسه n)؟
- هيشتغل عادي
- slow هيقف على الـ target مش قبله، فهيمسح الـ node اللي بعده، ولما
n = 1هيضرب TypeError - slow هيقف قبل الـ target بخطوتين
- infinite loop
الشرط الجديد بيخلّي الاتنين يمشوا خطوة زيادة. الـ combo الصح: gap = n مع fast.next !== null، أو gap = n + 1 مع fast !== null.
في Linked List Cycle، ليه fast مستحيل «ينط» فوق slow جوه الدايرة من غير ما يقابله؟
- عشان الدايرة طولها زوجي دايمًا
- عشان المسافة بينهم بتقل 1 بالظبط كل خطوة، فلازم توصل صفر
- هو ممكن ينط فوقه، بس هيتقابلوا في اللفة الجاية
- عشان slow بيقف لما fast يقرّب
fast بيتحرك 2 و slow بيتحرك 1، فالفرق بينهم بيقل 1 كل خطوة: 3، 2، 1، 0. مفيش فرصة يعدّي من 1 لـ -1 من غير ما يعدّي على 0.
إيه الـ space complexity بتاعة reverseListRec على list فيها n node؟
- O(1)، مفيش ولا array
- O(log n)
- O(n)، عشان كل نداء ليه frame على الـ call stack لحد ما نوصل للآخر
- O(n²)
الدالة بتنادي نفسها n مرة قبل ما أي نداء يرجع، فالـ stack بيبقى فيه n frame في نفس اللحظة. ده اللي هتشوفه متحرّك في فصل الـ Recursion.
تمرين: فكّر قبل ما تفتح
هل الـ list بتتقري زي ما هي من الناحيتين؟ تقدر تعملها في O(n) وقت و O(1) memory؟
تلميح 1
الحل السهل: انسخ القيم في array واعمل two pointers من الطرفين. ده O(n) memory. عشان O(1): محتاج تقرا النص التاني من الآخر للأول. افتكر Reorder List.
تلميح 2
لاقي آخر النص الأول بالنسخة B، واعكس اللي بعده، وقارن النصين node node. لو الطول فردي، النص الأول أطول بواحدة (اللي في النص)، فقف لما النص التاني يخلص.
الحل
الخطوة 4 مش لازمة عشان الـ judge، بس في الانترفيو قول إنك بترجّع الـ input زي ما كان. دالة اسمها isPalindrome المفروض ما تبوّظش الـ list اللي اتبعتتلها.
لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.
اتمرن على LeetCode بالترتيب
كل مسألة بتضيف فكرة واحدة على اللي قبلها. ارسم مربعات وأسهم على ورقة قبل ما تكتب. لو قعدت أكتر من 25 دقيقة، ارجع للقالب هنا، وبعدين حاول تاني من غير ما تبص.
- Reverse Linked Listالمثال المحلول 1. اكتبه من دماغك لحد ما الـ 4 سطور يبقوا reflex.
- Middle of the Linked Listfast & slow، النسخة A.
- Remove Duplicates from Sorted Listdelete بالـ prev من غير dummy، لأن الـ head عمره ما بيتمسح هنا.
- Remove Linked List Elementsنفس الفكرة، بس الـ head ممكن يتمسح: dummy.
- Merge Two Sorted Listsالمثال المحلول 2: dummy + tail.
- Linked List Cyclefast & slow للدواير. قارن الـ nodes مش القيم.
- Palindrome Linked Listالتمرين اللي فوق: middle + reverse + compare.
- Intersection of Two Linked Listsفكرة جديدة: pointer لما يخلص list يكمّل في التانية، فالاتنين يمشوا نفس المسافة.
- Remove Nth Node From End of Listالمثال المحلول 3: gap ثابت + dummy.
- Add Two Numbersبناء list جديدة بـ dummy + tail، ومعاها carry زي الجمع في المدرسة.
- Linked List Cycle IIالمثال المحلول 4. اكتب المعادلة من دماغك قبل الكود.
- Reorder Listالمثال المحلول 5: تلات أدوات في مسألة واحدة.
- Reverse Linked List IIreverse لجزء في النص: dummy + اربط الطرفين بعد العكس.
- Reverse Nodes in k-Groupاختياري: Reverse II بتتكرر كل k. لو حليتها يبقى الأسهم بقت في إيدك.
وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.
الخلاصة
.next من null، وتحط dummy لما الـ head ممكن يتغيّر.
| السؤال | الإجابة |
|---|---|
cur !== null ولا cur.next !== null؟ | الأول لو عايز تعالج كل node. التاني لو عايز تقف على آخر node أو قبل الـ candidate، وساعتها لازم cur ما يبقاش null من الأول (dummy). |
| إمتى dummy؟ | لما الـ head ممكن يتمسح أو يتغيّر، أو بتبني list جديدة. |
| إمتى fast & slow؟ | النص، أو الدايرة. والنسخة B (fast.next.next) لما عايز تقسم نصّين. |
| إمتى gap ثابت؟ | الـ node رقم k من الآخر في لفة واحدة. |
| iterative ولا recursive؟ | الـ iterative O(1) memory. الـ recursive أقصر بس O(n) stack، وبيقع مع lists كبيرة. |
| بقارن إزاي؟ | الـ nodes بـ === (نفس الـ object). القيم بـ .val. |
الفصل الجاي: Recursion. لو بصيت للـ linked list تاني، هتلاقيها recursive من جواها: الـ list = node + list أصغر بتبدأ من head.next. عشان كده الـ reverse اتكتب في 5 سطور recursive. هناك هتفهم الـ call stack وإزاي «تثق في الدالة»، وبعدها على طول الـ trees: linked list كل node فيها اتنين next بدل واحد، left و right.