Linked ListListNode · head · traversal · dummy node · reverse · fast & slow

الـ array بتحط العناصر جنب بعض في الـ memory. الـ linked list بتفرّقهم في أي حتة، وكل عنصر ماسك عنوان اللي بعده. الفكرة البسيطة دي بتخلّي الـ insert والـ delete O(1)، وبتفتح باب مسائل كلها لعب بالأسهم: reverse، و merge، ودواير.

قبله: Queue و Deque و Two Pointers بيمهّد لـ: Recursion و Binary Trees

هتطلع من الفصل ده وإنت عارف

  • يعني إيه 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 نفسها:

تشبيه في لعبة البحث عن الكنز، مش معاك خريطة. معاك ورقة واحدة مكتوب فيها مكان الورقة الجاية، وهكذا لحد آخر ورقة مكتوب فيها «خلصت». ده بالظبط الـ linked list: الـ 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. السؤال الحقيقي: أنهي حيلة؟ الكلمات دي بتوجّهك:

لما تشوف: head of a linked listListNodereversemerge sorted lists middle of the listcyclen-th node from the endremove nodes reorder / rearrangeO(1) extra memorypalindrome list
ومش linked list غالبًا لو: access by index كتيرbinary search

لو المسألة محتاجة random access أو binary search، الـ list هتبقى بطيئة لأن الوصول للنص لوحده O(n). ساعتها حوّلها لـ array الأول.

الموقفالحيلةأشهر مسائل
تمشي على كل node، تعدّ، تدوّرcur واحد بيمشي لحد nullRemove Duplicates from Sorted List
الـ head ممكن يتمسح أو يتغيّر، أو بتبني list جديدةdummy node قبل الـ headRemove Elements، Merge Two Lists، Remove Nth، Add Two Numbers
الترتيب لازم يتعكسprev و cur و nextReverse List، Reverse List II، Palindrome List
النص، أو فيه دايرةfast & slowMiddle، Cycle I و II
الـ node رقم k من الآخراتنين pointers بينهم gap ثابتRemove Nth From End
مسألة كبيرةتركيبة: middle + reverse + mergeReorder 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، وأي حاجة تانية مجرد حركة أسامي.

  1. نفس التعريف اللي LeetCode بيكتبهولك في كومنت فوق الحل. في الاختبار مش هتكتبه، بس هتحتاجه وإنت بتجرّب على جهازك.
  2. الـ defaults بتخلّي new ListNode(5) node لوحدها، و new ListNode() تنفع dummy. وليه null مش undefined؟ لأن شروطك كلها cur !== null، و undefined !== null بتطلع true، فهتكمّل وتضرب TypeError.
  3. ده كل اللي جوه الـ node. هي مش عارفة مين قبلها، ولا الـ list طولها كام.
  4. تلات nodes منفصلين، كل واحدة الـ next بتاعها null. لسه مفيش list.
  5. هنا بنربط: «السهم اللي جوه a يشاور على b». الترتيب هنا مش فارق، بس في الـ insert والـ reverse هيبقى كل حاجة.
  6. مفيش object اسمه List. الـ list = reference لأول node. ضيّعت الـ head يبقى ضيّعت الـ list، ومفيش .length: عايز الطول؟ امشي وعدّ.
العمليةArrayLinked Listليه
الوصول للعنصر رقم iO(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 زيادة
في نوع تاني: doubly linked list كل node فيها prev كمان، فتمشي في الاتجاهين وتمسح node لوحدها من غير ما تدوّر على اللي قبلها. هتقابلها في LRU Cache (doubly linked list + hash map). أغلب مسائل LeetCode singly: next بس، وده موضوع الفصل.

عندنا list. أول حاجة هنعملها عليها: نمشي عليها من أولها لآخرها من غير ما نوقع في null.

المشي على الـ list (traversal)

أهم 4 سطور في الفصل. أي عدّ أو جمع أو بحث على list بيبدأ بيهم. هنكتبهم كـ toArray لأننا هنحتاجها بعدين عشان نجرّب حلولنا:

  1. ليه cur وما نمشيش بالـ head نفسه؟ لو حرّكت head، بعد الـ loop هيبقى null وضيّعت أول الـ list. خليها عادة: الـ head ثابت، و cur هو اللي بيمشي.
  2. ليه cur !== null مش cur.next !== null؟ التاني بيقف على آخر node من غير ما يعالجها (هتطلّع [5, 1, 8] بس)، وعلى list فاضية بيضرب TypeError. الأول بيشتغل حتى لو head === null: الـ loop مش هتدخل والإجابة [].
  3. ده مكان الشغل: هنا push، وفي مسائل تانية عدّ أو مقارنة.
  4. ده الـ i++ بتاع الـ linked list. نسيته؟ infinite loop.
  5. كل node اتزارت مرة واحدة، فالوقت O(n).
قاعدة الـ null قبل ما تكتب 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 تقدر تروح لقدّام بس.

  1. node لوحدها، الـ next بتاعها null. مكانها في الـ memory مش مهم.
  2. ده لازم الأول. الـ node الجديدة تمسك باقي الـ list وهو لسه متاح في prev.next. لو بدّلت السطرين، prev.next هيبقى الـ node نفسها، فـ node.next = prev.next هيخليها تشاور على نفسها: cycle، والـ list اتقطعت.
  3. دلوقتي بس نحوّل سهم prev. الـ rule: امسك اللي قدّام قبل ما تسيب.
  4. guard: لو prev آخر node، مفيش حاجة نمسحها، ومن غيره prev.next.next هيضرب TypeError.
  5. الـ 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 هو العقدة دي، و dummy.next هو أول حباية.
  1. قيمته مش مهمة، عمرنا ما هنقراها. المهم إنه بيشاور على الـ head، فالـ head بقى ليه prev.
  2. cur بيبدأ من الـ dummy مش الـ head، لأننا دايمًا واقفين قبل الـ candidate. كده أول candidate هو الـ head نفسه.
  3. cur.next !== null عشان محتاجين candidate. و cur نفسه عمره ما بيبقى null: بيبدأ من dummy، وبيتحرك بس لـ node اتشيكنا إنها مش null.
  4. ليه ما بنحرّكش cur بعد الـ delete؟ لأن cur.next الجديد candidate جديد لسه ما اتشيكش. في 6 → 6 لو اتحركت هتعدّي التانية من غير ما تمسحها.
  5. بنتحرك بس لما الـ node تفضل.
  6. dummy.next مش head: المتغير head لسه بيشاور على أول node الأصلية، وممكن تكون اتمسحت.
إمتى dummy؟ أي مسألة الـ head فيها ممكن يتمسح أو يتغيّر، أو بتبني فيها list جديدة: ابدأ بـ const dummy = new ListNode(0) واختم بـ return dummy.next.

أول استخدام عملي للـ dummy: نبني list من array عشان نجرّب حلولنا على جهازنا.

تبني list من array عشان تجرّب

على LeetCode الـ judge بيبني الـ list من [1,2,3] ويبعتلك الـ head. على جهازك إنت اللي هتعمل ده، ونفس حيلة الـ dummy بتخلّي الكود 6 سطور:

  1. من غيره، أول append special case: if (head === null) head = node; else tail.next = node;.
  2. tail = آخر node لحد دلوقتي. من غيره كل append هيمشي من الـ head للآخر، يعني O(n) لكل عنصر و O(n²) للكل.
  3. نعلّق الجديدة ونقدّم الـ tail عليها. نفس ترتيب «امسك وبعدين اتحرك».
  4. لو 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 يبقى قطع نص المسافة. هنا هنقف عند تفصيلة بتفرق في المسائل: لو الطول زوجي فيه نصّين، تاخد أنهي واحد؟

  1. ليه شرطين؟ fast هيعمل fast.next.next، فلازم fast و fast.next الاتنين موجودين. والترتيب مهم: الـ && بيعمل short-circuit، فلو fast === null الجزء التاني مش بيتحسب أصلًا. اقلبهم وهتضرب TypeError.
  2. slow خطوة و fast خطوتين، فـ fast دايمًا قاطع ضعف slow.
  3. طول فردي: النص بالظبط. طول زوجي: النص التاني (4 في 1..6).
  4. بيبص خطوة لقدّام زيادة، فبيقف بدري بخطوة. طول زوجي: النص الأول (3 في 1..6). خلي بالك: fast.next على head = null هيضرب error، فاللي بينادي لازم يتشيك على الـ list الفاضية الأول.
  5. ده آخر node في النص الأول، و slow.next أول النص التاني. ده اللي هنحتاجه في Reorder و Palindrome عشان نقسم الـ list.
الـ listA: middleNodeB: endOfFirstHalf
1 → 2 → 3 → 4 → 533
1 → 2 → 3 → 4 → 5 → 643
1 → 221
111

كده الأدوات كلها معانا. نبدأ المسائل بأشهر واحدة فيهم، واللي كل الباقي مبني عليها: reverse.

مثال محلول 1: Reverse Linked List

Reverse Linked List

easyLeetCode 206

معاك الـ head بتاع linked list. اقلب اتجاه كل الأسهم، ورجّع الـ head الجديد.

Input: 1 -> 2 -> 3 -> 4 Output: 4 -> 3 -> 2 -> 1 Input: 7 -> 9 Output: 9 -> 7 Input: (empty, head = null) Output: null

نفكّر فيها مع بعض

  1. افهم المطلوب: مش هنعمل list جديدة، هنقلب الأسهم نفسها. كل node كانت بتشاور على اللي بعدها، هتشاور على اللي قبلها، وأول node هتبقى آخر واحدة فالـ next بتاعها null.
  2. Brute force: نحط القيم في array، ونمشي تاني نكتبها بالعكس. O(n) وقت بس O(n) memory، وبيغيّر القيم مش الـ nodes.
  3. الـ key insight: نمشي مرة واحدة ونقلب سهم كل node. بس الـ list one-way، فمحتاجين نفتكر اللي قبل (prev). ولما نقلب سهم cur هنضيّع الطريق لباقي الـ list، فلازم نحفظه في next قبل ما نقلب.
  4. الخطة: 3 pointers و 4 سطور بترتيب ثابت في كل لفة: احفظ، اقلب، قدّم prev، قدّم cur.
  5. Edge cases: list فاضية ترجع null، و node واحدة ترجع نفسها.
  1. ليه null؟ أول node هتبقى الأخيرة، والأخيرة الـ next بتاعها لازم null. لو بدأت prev = head، أول node هتشاور على نفسها.
  2. cur !== null عشان نقلب كل node بما فيها الأخيرة. ولو الـ list فاضية الـ loop مش هتدخل ونرجّع null صح.
  3. الـ reference الوحيد لباقي الـ list هو cur.next، والسطر الجاي هيكتب فوقه. احفظه الأول.
  4. ده السطر الوحيد اللي بيغيّر الـ list فعلًا. الباقي كله حركة أسامي.
  5. الترتيب مهم: prev = cur قبل cur = next، وإلا prev هياخد قيمة next. و cur = next مش cur.next، لأن cur.next دلوقتي بيشاور لورا.
  6. بعد الـ loop cur بقى null، و prev واقف على آخر node الأصلية، وهي الـ head الجديد. مش head: ده بقى آخر واحدة.

ده أهم animation في الفصل. كل سطر خطوة، وكل pointer move لوحده. بص على السهم الأصفر وهو بيتقلب:

Inputالمتوقعليه الحالة دي مهمة
nullnullالـ loop مش بتدخل، و prev لسه null
55لفة واحدة: 5.next = null وترجع 5
7 -> 99 -> 7أصغر list فيها سهم يتقلب فعلًا

التعقيد: كل node بتتزار مرة، يعني O(n) وقت و O(1) memory (3 متغيرات بس).

النسخة الـ recursive

نفس المسألة ليها حل recursive قصير. هنا الكود والفكرة، والـ call stack متحرّك خطوة بخطوة في فصل الـ Recursion:

  1. الـ base case: list فاضية أو node واحدة معكوسة أصلًا.
  2. ثق إن النداء ده عكس كل اللي بعد head. head.next لسه بيشاور على نفس الـ node، وهي بقت آخر الجزء المعكوس.
  3. خلّي الـ node دي تشاور لورا على head.
  4. وقطّع السهم القديم، وإلا الاتنين هيشاوروا على بعض: cycle.
  5. الـ head الجديد (آخر node أصلية) بيرجع زي ما هو من كل مستوى.
في الانترفيو الـ recursive أقصر، بس بياخد O(n) memory على الـ call stack، ومع list طويلة (من حوالي 10 لـ 15 ألف node في Node.js، حسب حجم الـ frame) هيضرب stack overflow. الـ iterative O(1). اكتب الـ iterative، وارسم مربعات وأسهم وإنت بتشرح، وقول الـ 4 خطوات بصوت عالي: «احفظ، اقلب، قدّم، قدّم».

الـ reverse بيعدّل list واحدة. طب لو عندك اتنين وعايز تعمل منهم list جديدة؟

مثال محلول 2: Merge Two Sorted Lists

الجديد هنا إننا بنبني list جديدة من nodes جاية من اتنين lists، فهنستخدم الـ dummy مع pointer اسمه tail، زي buildList بالظبط.

Merge Two Sorted Lists

easyLeetCode 21

عندك list1 و list2، كل واحدة مترتبة تصاعدي. ادمجهم في list واحدة مترتبة باستخدام نفس الـ nodes (من غير ما تعمل nodes جديدة)، ورجّع الـ head.

list1 = 1 -> 5 -> 6, list2 = 2 -> 3 -> 8 -> 9 → 1 -> 2 -> 3 -> 5 -> 6 -> 8 -> 9 list1 = null, list2 = 0 → 0 list1 = null, list2 = null → null

نفكّر فيها مع بعض

  1. Brute force: نجمع كل القيم في array، نعمل sort، ونبني list جديدة. O((n+m) log(n+m))، وبيعمل nodes جديدة والمسألة عايزة نفس الـ nodes.
  2. الـ key insight: أصغر عنصر فاضل لازم يكون واحد من الـ two heads. فنقارن الاتنين، وناخد الأصغر، ونقدّم في الـ list بتاعته بس. ده نفس الـ merge step بتاع merge sort.
  3. مين الـ head بتاع النتيجة؟ مش عارفين قبل أول مقارنة، وده special case. فنبدأ بـ dummy، ونعلّق عليه بـ tail.
  4. لما list تخلص: الباقي من التانية مترتب ومربوط أصلًا، وكله أكبر من أو يساوي اللي أخدناه. نعلّقه كله في خطوة واحدة، من غير loop.
  5. Edge cases: واحدة أو الاتنين فاضيين، قيم متساوية، أطوال مختلفة.
  1. الـ dummy بيشيل سؤال «النتيجة فاضية ولا لأ؟». و tail = آخر node في النتيجة.
  2. &&: بنقارن بس طول ما الاتنين فيهم nodes. أول ما واحدة تخلص، مفيش حاجة نقارنها.
  3. <= ولا <؟ الاتنين صح للقيم. الـ <= بياخد من list1 في التساوي، فبيحافظ على ترتيب المتساويين (stable)، وده بيفرق لما الـ nodes شايلة data تانية.
  4. بنعلّق الـ node نفسها (من غير copy) ونقدّم list1. السهم القديم بتاعها لسه بيشاور جوه list1، ومش مشكلة: هيتكتب فوقه في اللفة الجاية أو في سطر 14.
  5. برا الـ if/else لأنه مشترك في الفرعين.
  6. واحدة على الأقل خلصت. علّق الباقي من التانية كله مرة واحدة. ولو الاتنين null هيعلّق null، وده صح.
  7. الـ head الحقيقي، أيًّا كان جه من أنهي list.

في الـ animation، list1 باللون الأزرق و list2 بالأصفر، والأسهم الخضرا هي النتيجة وهي بتتبني:

Inputالمتوقعليه الحالة دي مهمة
null, nullnullالـ loop مش بتدخل، و dummy.next = null
null, 00سطر 14 لوحده بيحلها
2 -> 2, 22 -> 2 -> 2التساوي: <= بياخد من list1 الأول
1 -> 2 -> 3, 7 -> 81 -> 2 -> 3 -> 7 -> 8list1 بتخلص كلها الأول، و 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.

Remove Nth Node From End of List

mediumLeetCode 19

امسح الـ node رقم n من آخر الـ list ورجّع الـ head. الـ n دايمًا valid: من 1 لحد الطول.

head = 3 -> 8 -> 1 -> 9 -> 4, n = 2 → 3 -> 8 -> 1 -> 4 (9 is 2nd from the end) head = 3 -> 8 -> 1 -> 9 -> 4, n = 5 → 8 -> 1 -> 9 -> 4 (the head itself) head = 7, n = 1 → null

نفكّر فيها مع بعض

  1. افهم المطلوب: لو الطول L، فرقم n من الآخر هو رقم L - n + 1 من الأول. وعشان نمسحه محتاجين اللي قبله.
  2. حل بلفّتين: لفة تعدّ L، ولفة تمشي من الـ dummy L - n خطوة. ده O(L) وحل كويس تمامًا. الـ follow-up بيطلب لفة واحدة.
  3. الـ key insight: خلّي fast يسبق slow بـ n خطوة، وبعدين حرّكهم مع بعض. الـ gap ثابت، فلما fast يقف على آخر node، slow هيبقى قبل الـ target بالظبط.
  4. ليه من الـ dummy؟ لو n = L الـ target هو الـ head، ومحتاجين node قبله. slow هيفضل واقف على الـ dummy.
  5. Edge cases: n = L (الـ head)، n = 1 (آخر node)، list من node واحدة.
تشبيه إنت ماسك عصاية طولها ثابت وماشي في شارع. أول ما طرفها الأمامي يخبط في آخر الشارع، طرفها الخلفي هيبقى على بعد طول العصاية من الآخر بالظبط. مش محتاج تعرف الشارع طوله كام.
  1. الاتنين من الـ dummy، عشان لو الـ target هو الـ head، slow يبقى ليه مكان يقف فيه قبله.
  2. i < n يعني n خطوة بالظبط. fast مش هيبقى null هنا، لأن n ≤ L و الـ dummy + L nodes.
  3. الـ off-by-one كله هنا. فيه combo صح من اتنين: (gap = n ونقف لما fast.next === null) أو (gap = n + 1 ونقف لما fast === null). لو خلطتهم، slow هيقف على الـ target مش قبله.
  4. الاتنين خطوة، فالـ gap ثابت.
  5. slow.next هو الـ target، ومش null لأن الـ gap ≥ 1. نطّ فوقه.
  6. الـ head ممكن يكون هو اللي اتمسح، فـ dummy.next.
Inputالمتوقعليه الحالة دي مهمة
3 -> 8 -> 1 -> 9 -> 4, n = 58 -> 1 -> 9 -> 4الـ head اتمسح: slow فضل على الـ dummy
3 -> 8 -> 1 -> 9 -> 4, n = 13 -> 8 -> 1 -> 9آخر node: slow.next.next = null
7, n = 1nullالـ list فضيت: dummy.next = null

التعقيد: fast بيمشي الـ list مرة واحدة: O(L) وقت، لفة واحدة، و O(1) memory.

الـ gap كان ثابت. طب لو الاتنين بسرعات مختلفة، ممكن نكتشف إن الـ list ليها آخر أصلًا؟

مثال محلول 4: Linked List Cycle I و II

الجديد هنا: fast & slow مش بس بيلاقوا النص، بيكشفوا دايرة. وفي الجزء التاني فيه شوية رياضة بسيطة بتقولك الدايرة بتبدأ فين.

Linked List Cycle

easyLeetCode 141

هل الـ list فيها دايرة؟ يعني لو فضلت تمشي بـ next، هترجع لـ node عدّيت عليها بدل ما توصل null؟

Linked List Cycle II

mediumLeetCode 142

نفس الكلام، بس رجّع الـ node اللي الدايرة بتبدأ عندها، أو null لو مفيش. من غير ما تعدّل الـ list.

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7, and 7.next = 3 → 141: true, 142: node 3 1 -> 2 -> 3 → 141: false, 142: null 1, and 1.next = 1 → 141: true, 142: node 1

نفكّر فيها مع بعض

  1. Brute force: Set فيه الـ nodes اللي زرناها. أول node تتكرر هي بداية الدايرة. O(n) وقت و O(n) memory. خلي بالك: بنخزّن الـ nodes نفسها مش القيم، لأن القيم ممكن تتكرر.
  2. من غير memory: fast & slow. لو مفيش دايرة، fast هيوصل null. لو فيه، الاتنين هيدخلوها، و fast بيقرّب من slow node واحدة كل خطوة، فلازم يحصّله.
  3. ليه fast مش بينط فوق slow؟ المسافة بينهم جوه الدايرة بتقل 1 بالظبط كل خطوة (fast +2، slow +1)، فلازم توصل صفر.
  4. للـ 142: مكان المقابلة مش بالضرورة البداية. الرياضة تحت بتثبت: رجّع pointer للـ head، وحرّك الاتنين one step، هيتقابلوا عند البداية.
  1. الاتنين من الـ head. لو head === null الـ loop مش هتدخل والإجابة false.
  2. نفس شرط middleNode: fast محتاج خطوتين متاحين.
  3. اتحرك الأول وبعدين قارن. في البداية الاتنين على الـ head، فلو قارنت قبل الحركة هترجع true على طول. و === على objects بيقارن الـ reference: node تانية قيمتها 5 مش «نفس الـ node».
  4. fast وصل null، يبقى الـ list ليها آخر.
الرياضة: ليه الرجوع للـ head بيلاقي البداية؟

سمّي: 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 لفة كاملة ترجّعه لنفس المكان. الاتنين بيوصلوا البداية في نفس اللحظة.

  1. phase 1 هي hasCycle بالظبط.
  2. pointer جديد من الـ head. ده الـ a خطوة اللي في المعادلة.
  3. while مش do: لو الدايرة بادئة من الـ head (a = 0)، المقابلة بتكون عند الـ head، والـ loop مش هتدخل.
  4. الاتنين one step. لو slow فضل بيمشي خطوتين، المعادلة تبوظ ومش هيتقابلوا عند البداية.
  5. البداية. ورجّعنا node، مش index ولا قيمة.

المثال: a = 2 (الـ 1 والـ 2 قبل الدايرة)، والدايرة 3 → 4 → 5 → 6 → 7 → 3 طولها c = 5. شوف الأرقام وهي بتطلع:

Input141142ليه الحالة دي مهمة
nullfalsenullالـ loop مش بتدخل
1 -> 2 -> 3falsenullfast بيوصل null
1, 1.next = 1true1self-loop: a = 0 و c = 1
1 -> 2 -> 3, 3.next = 1true1الدايرة من الـ head: phase 2 بترجع على طول

التعقيد: phase 1 أقل من a + c خطوة لـ slow، و phase 2 بالظبط a خطوة. يعني O(n) وقت و O(1) memory.

في الانترفيو ابدأ بالـ Set، وقول إنه 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 بالتبادل.

Reorder List

mediumLeetCode 143

عندك L0 → L1 → … → Ln. رتّبها تبقى L0 → Ln → L1 → Ln-1 → L2 → …: واحدة من الأول وواحدة من الآخر بالتبادل. عدّل الـ nodes نفسها مش القيم، والدالة مش بترجّع حاجة.

1 -> 2 -> 3 -> 4 -> 5 -> 6 → 1 -> 6 -> 2 -> 5 -> 3 -> 4 1 -> 2 -> 3 -> 4 -> 5 → 1 -> 5 -> 2 -> 4 -> 3

نفكّر فيها مع بعض

  1. Brute force: حط الـ nodes (الـ references) في array، واعمل two pointers من الطرفين وانت بتربط. O(n) وقت و O(n) memory. إجابة أولى كويسة.
  2. المشكلة: محتاجين ناخد من الآخر، والـ list one-way. بس لو عكسنا النص التاني، Ln, Ln-1, … هتبقى بالترتيب العادي من الأول!
  3. الخطة: (1) لاقي آخر النص الأول بـ endOfFirstHalf. (2) اقطع الـ list، واعكس النص التاني. (3) ادمج بالتبادل: واحدة من هنا وواحدة من هنا.
  4. ليه نقطع؟ لو ما عملناش slow.next = null، آخر node في النص الأول هتفضل بتشاور جوه النص التاني، وبعد الدمج هيطلع cycle.
  5. Edge cases: 0 أو 1 أو 2 nodes: مفيش حاجة تتغيّر، بس الكود لازم ما يضربش.
  1. 0 أو 1 node: مفيش حاجة تترتب. والأهم إن النسخة B بتقرا fast.next، فلازم الـ head مش null.
  2. النسخة B من fast & slow: slow بيقف على آخر النص الأول، فالنص الأول ≥ التاني.
  3. نمسك أول النص التاني، وبعدين نقطع. نفس rule الـ insert: امسك قبل ما تسيب.
  4. ده reverseList حرفيًا، بس على second. بعدها prev = آخر node أصلية.
  5. ليه second !== null مش first؟ لأن النص التاني ≤ الأول. لما يخلص نقف، واللي فاضل من الأول (لو الطول فردي) في مكانه الصح ومربوط أصلًا.
  6. احفظ الاتنين الأول. السطرين الجايين هيكتبوا فوق first.next و second.next.
  7. دخّل second بين first واللي كان بعدها.
  8. قدّم الاتنين للزوج الجاي.

الأزرق النص الأول، والأصفر النص التاني. خلي بالك من لحظة القطع:

التعقيد: 3 لفّات كل واحدة ≤ n، يعني O(n) وقت و O(1) memory.

في الانترفيو قول الخطة بصوت عالي قبل ما تكتب: «middle، reverse، merge». ولو الوقت يسمح، اكتب كل خطوة كـ helper منفصلة. الـ interviewer بيقيّم هنا إنك بتقسم المسألة، مش إنك حافظ الحل.

في كل مثال كان فيه سطر واحد لو غلط بيبوّظ كل حاجة. يلا نجمع الغلطات دي في مكان واحد.

غلطات مشهورة

كل غلطة هنا سطر واحد، والنتيجة يا 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.

تمرين: فكّر قبل ما تفتح

Palindrome Linked List

easyLeetCode 234

هل الـ list بتتقري زي ما هي من الناحيتين؟ تقدر تعملها في O(n) وقت و O(1) memory؟

1 -> 2 -> 2 -> 1 → true 1 -> 2 -> 3 -> 2 -> 1 → true 1 -> 2 → false
تلميح 1

الحل السهل: انسخ القيم في array واعمل two pointers من الطرفين. ده O(n) memory. عشان O(1): محتاج تقرا النص التاني من الآخر للأول. افتكر Reorder List.

تلميح 2

لاقي آخر النص الأول بالنسخة B، واعكس اللي بعده، وقارن النصين node node. لو الطول فردي، النص الأول أطول بواحدة (اللي في النص)، فقف لما النص التاني يخلص.

الحل

الخطوة 4 مش لازمة عشان الـ judge، بس في الانترفيو قول إنك بترجّع الـ input زي ما كان. دالة اسمها isPalindrome المفروض ما تبوّظش الـ list اللي اتبعتتلها.

لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.

اتمرن على LeetCode بالترتيب

كل مسألة بتضيف فكرة واحدة على اللي قبلها. ارسم مربعات وأسهم على ورقة قبل ما تكتب. لو قعدت أكتر من 25 دقيقة، ارجع للقالب هنا، وبعدين حاول تاني من غير ما تبص.

وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.

الخلاصة

في جملة واحدة الـ linked list = nodes ماسكة في بعض بأسهم. كل الشطارة إنك تغيّر الأسهم بالترتيب الصح (امسك اللي قدّام قبل ما تسيب)، وتحمي كل .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.