الكشف عن بداية حلقة في قائمة ارتباط مرتبطة منفردة؟

Question

هل هناك أي طريقة لمعرفة بداية حلقة في قائمة الارتباطات باستخدام ليس أكثر من مؤشرين؟لا أرغب في زيارة كل عقدة وأن أميزها وأبلغت عن العقدة الأولى التي شوهدت بالفعل. هل هناك أي طريقة أخرى للقيام بذلك؟

Answer 1

لقد سمعت هذا السؤال الدقيق كمسألة اختبار للمقابلة.

الحل الأكثر أناقة هو:

ضع كلا المؤشرتين في العنصر الأول (اتصل بهما A و B)

ثم استمر في الحلقات ::

• تقدم إلى العنصر التالي
• تقدم A إلى العنصر التالي مرة أخرى
• تقدم ب إلى العنصر التالي

في كل مرة تقوم فيها بتحديث مؤشر ، تحقق مما إذا كانت A و B متطابقة. إذا كانت المؤشرات A و B في مرحلة ما متطابقة ، فأنت لديك حلقة. المشكلة في هذا النهج هي أنه قد ينتهي بك الأمر إلى التحرك حول الحلقة مرتين ، ولكن ليس أكثر من مرتين مع المؤشر أ

إذا كنت ترغب في العثور على العنصر الذي له مؤشران يشيران إليه ، فهذا أكثر صعوبة. كنت أخرج من أحد الأطراف وأقول إنه من المستحيل القيام به مع اثنين من المؤشرتين فقط إلا إذا كنت على استعداد لتكرار اتباع القائمة المرتبطة بعدد كبير من المرات.

الطريقة الأكثر فعالية للقيام بذلك بمزيد من الذاكرة ، هي وضع المؤشرات على العناصر في الصفيف ، وفرزها ، ثم ابحث عن التكرار.

Answer 2

الخطوة 1: تابع بالطريقة المعتادة ، ستستخدم للعثور على الحلقة ، أي أن لديك مؤشران ، وزيادة واحدة في خطوة واحدة وغيرها في خطوتين ، إذا التقى كلاهما في وقت ما ، هناك حلقة.

الخطوة 2: قم بتجميد مؤشر واحد حيث كان وزيادة المؤشر الآخر في خطوة واحدة لحساب الخطوات التي تتخذها وعندما يجتمع كلاهما مرة أخرى ، سيعطيك العدد طول الحلقة (وهذا هو نفس عدد العناصر في رابط دائري قائمة).

الخطوه 3: أعد تعيين كلا المؤشرتين إلى بداية قائمة الارتباطات ، وزيادة مؤشر واحد إلى طول أوقات الحلقة ثم ابدأ المؤشر الثاني. زيادة كلا المؤشرتين في خطوة واحدة وعندما يجتمعون مرة أخرى ، ستكون بداية الحلقة (وهذا هو نفسه العثور على n^العاشر عنصر من نهاية قائمة الارتباط).

Answer 3

دليل رياضي + الحل

Let 'k' be the number of steps from HEADER to BEGINLOOP.
Let 'm' be the number of steps from HEADER to MEETPOINT.
Let 'n' be the number of steps in the loop.
Also, consider two pointers 'P' and 'Q'. Q having 2x speed than P.

حالة بسيطة: عندما يكون k <n

عندما يكون المؤشر "P" في BeginLoop (أي أنه كان سيسافر "K") ، فإن Q قد سافرت خطوات "2K". لذلك ، على نحو فعال ، فإن Q قبل خطوات "2K-K = K" من P عندما تدخل P الحلقة ، وبالتالي ، Q هي خطوات "NK" وراء BeginLoop الآن.

عندما كان P قد انتقلت من BeginLoop إلى MeetPont ، كان من الممكن أن يسافر خطوات "MK". في ذلك الوقت ، كانت س سافرت خطوات "2 (MK)". ولكن ، نظرًا لأنهم التقيا ، وبدأت Q في خطوات "NK" خلف Leghloop ، لذلك ، على نحو فعال ، "2 (MK) - (NK)" يجب أن تكون مساوية لـ "(MK)" لذلك ،

=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m

هذا يعني أن P و Q يلتقيان عند النقطة المساوية لعدد الخطوات (أو متعددة لتكون عامة ، انظر الحالة المذكورة أدناه) في الحلقة. الآن ، في Meetpoint ، كل من P و Q هما خطوات "N- (MK)" خلفها ، أي ، "K" خلفها ، كما رأينا n = m. لذلك ، إذا بدأنا P من Header مرة أخرى ، و Q من Meetpoint ، ولكن هذه المرة مع وتيرة تساوي P و P و Q سوف يجتمع الآن في BeginLoop فقط.

الحالة العامة: قل ، k = nx + y ، y <n(وبالتالي ، K ٪ n = y)

عندما يكون المؤشر "P" في BeginLoop (أي أنه كان سيسافر "K") ، فإن Q قد سافرت خطوات "2K". لذلك ، على نحو فعال ، فإن Q قبل خطوات "2K-K = K" من P عندما يدخل P الحلقة. ولكن ، يرجى ملاحظة أن "K" أكبر من "N" ، مما يعني أن Q كان من شأنه أن يقوم بجولات متعددة من الحلقة. لذلك ، على نحو فعال ، Q هي خطوات "n- (k ٪ n)" خلف البداية الآن.

عندما كان P قد انتقلت من BeginLoop إلى MeetPoint ، كان من الممكن أن يسافر خطوات "MK". (وبالتالي ، على نحو فعال ، سيكون MeetPoint في خطوات "(MK) ٪ N 'قبل أن تبدأ Leghloop الآن.) في ذلك الوقت ، كان سافر" 2 (MK) ". ولكن ، نظرًا لأنهم التقوا ، وبدأت Q في خطوات "n- (k ٪ n)" وراء البداية ، لذلك ، بفعالية ، الموضع الجديد لـ Q (وهو (2 (mk) - (nk/٪ n)) ٪ n "من BeginLoop) يجب أن يكون مساوياً للموضع الجديد لـ P (وهو" (MK) ٪ n 'من حلقة البداية).

لذا،

=> (2(m - k) - (n - k%n))%n = (m - k)%n
=> (2(m - k) - (n - k%n))%n = m%n - k%n
=> (2(m - k) - (n - Y))%n = m%n - Y   (as k%n = Y)
=> 2m%n - 2k%n - n%n + Y%n = m%n - Y
=> 2m%n - Y - 0 + Y = m%n - Y    (Y%n = Y as Y < n)
=> m%n = 0
=> 'm' should be multiple of 'n'

Answer 4

أولاً ، نحاول معرفة ذلك ، هل هناك أي حلقة في القائمة أم لا. في حالة وجود حلقة ، نحاول معرفة نقطة انطلاق الحلقة. لهذا نستخدم مؤشرين هما slowptr و fastptr. في الكشف الأول (التحقق من الحلقة) ، يحرك Fastptr خطوتين مرة واحدة ولكن Slowptr يتحرك بخطوة واحدة إلى الأمام مرة واحدة.

slowPtr   1   2   3   4   5   6   7
fastPtr   1   3   5   7   9   5   7

من الواضح أنه إذا كان هناك أي حلقة في القائمة ، فسوف يجتمعون عند النقطة (النقطة 7 في الصورة أعلاه) ، لأن مؤشر Fastptr يعمل بشكل أسرع مرتين من غيره.

الآن ، وصلنا إلى مشكلة ثانية لإيجاد نقطة انطلاق الحلقة.

لنفترض أنهم يجتمعون في النقطة 7 (كما هو مذكور في الصورة أعلاه). بعد ذلك ، يخرج Slowptr من الحلقة ويقف في بداية القائمة يعني في النقطة 1 ولكن Fastptr لا يزال في نقطة الاجتماع (النقطة 7). الآن نقارن قيمة كلا المؤشرتين ، إذا كانت هي نفسها ، فهي نقطة انطلاق حلقة وإلا فإننا نتحرك خطوة واحدة إلى الأمام (هنا يتحرك FastPtr أيضًا بخطوة واحدة في كل مرة) ومقارنة مرة أخرى حتى نجد نفس النقطة.

slowPtr   1   2   3   4
fastPtr   7   8   9   4

الآن يأتي سؤال واحد في الاعتبار ، كيف يمكن ذلك. لذلك هناك دليل رياضي جيد.

افترض:

m => length from starting of list to starting of loop (i.e 1-2-3-4)
l => length of loop (i.e. 4-5-6-7-8-9)
k => length between starting of loop to meeting point (i.e. 4-5-6-7)

Total distance traveled by slowPtr = m + p(l) +k
where p => number of repetition of circle covered by slowPtr

Total distance traveled by fastPtr = m + q(l) + k
where q => number of repetition of circle covered by fastPtr

Since,
fastPtr running twice faster than slowPtr

Hence,
Total distance traveled by fastPtr = 2 X Total distance traveled by slowPtr
i.e
m + q(l) + k = 2 * ( m + p(l) +k )
or, m + k = q(l) - p(l)
or, m + k = (q-p) l
or, m = (q-p) l - k

So,
If slowPtr starts from beginning of list and travels "m" length then, it will reach to Point 4 (i.e. 1-2-3-4)

and
fastPtr start from Point 7 and travels " (q-p) l - k " length then, it will reach to Point 4 (i.e. 7-8-9-4),
because "(q-p) l" is a complete circle length with " (q-p) " times.

مزيد من التفاصيل هنا

Answer 5

تابع بالطريقة المعتادة التي ستستخدمها للعثور على الحلقة. بمعنى آخر. لديك مؤشران ، زيادة واحدة في خطوة واحدة (Slowpointer) وغيرها في خطوتين (fastpointer) ، إذا كان كلاهما يجتمع في وقت ما ، هناك حلقة.

كما كنت قد أدركت بالفعل أن نقطة الاجتماع هي k خطوة قبل رأس الحلقة.

حيث k هو حجم جزء غير محدد من القائمة.

تحرك الآن ببطء إلى رأس الحلقة

ابق بسرعة عند نقطة الاصطدام

كل واحد منها هي خطوة K من بداية الحلقة (بطيئة من بداية القائمة حيث يكون بسرعة K STEP قبل رأس الحلقة- ارسم الصورة للحصول على الوضوح)

حركهم الآن بنفس السرعة - يجب أن يجتمعوا في Starting Loop

على سبيل المثال

slow=head
while (slow!=fast)
{
     slow=slow.next;
     fast=fast.next;
}

Answer 6

هذا رمز للعثور على بداية الحلقة في القائمة المرتبطة:

public static void findStartOfLoop(Node n) {

    Node fast, slow;
    fast = slow = n;
    do {
        fast = fast.next.next;
        slow = slow.next;
    } while (fast != slow);       

    fast = n;
    do {
        fast = fast.next;
        slow = slow.next;
    }while (fast != slow);

    System.out.println(" Start of Loop : " + fast.v);
}

Answer 7

هناك طريقتان للعثور على الحلقات في قائمة الارتباطات. 1. استخدم اثنين من خطوتين متقدمتين وخطوتين مسبقان آخران إذا كانت هناك حلقة ، في مرحلة ما ، يحصل كل من المؤشر على نفس القيمة ولا تصل أبدًا إلى NULL. ولكن إذا لم يكن هناك مؤشر حلقة يصل إلى فارغ في نقطة واحدة ولم يحصل كل من المؤشر على نفس القيمة. ولكن في هذا النهج ، يمكننا الحصول على حلقة في قائمة الارتباطات ، لكن لا يمكننا معرفة مكان بدء الحلقة بالضبط. هذه ليست الطريقة الفعالة كذلك.

2. استخدم وظيفة التجزئة بطريقة يجب أن تكون القيمة فريدة من نوعها. incase إذا كنا نحاول إدراج المكررة في ينبغي من خلال الاستثناء. ثم السفر عبر كل عقدة وادفع العنوان إلى التجزئة. إذا وصل المؤشر إلى NULL ولم يكن هناك استثناء من التجزئة يعني أنه لا توجد دورة في قائمة الارتباطات. إذا حصلنا على أي استثناء من التجزئة ، فهذا يعني وجود دورة في القائمة وهذا هو الرابط الذي تبدأ منه الدورة.

Answer 8

حسنًا ، لقد جربت طريقة باستخدام مؤشر واحد ... جربت الطريقة في العديد من مجموعات البيانات .... حيث يتم تخصيص ذاكرة كل من العقد في قائمة مرتبطة بترتيب متزايد ، لذلك أثناء عبور القائمة المرتبطة من رأس القائمة المرتبطة ، إذا أصبح عنوان العقدة أكبر من عنوان العقدة الذي يشير إليه ، فيمكننا تحديد وجود حلقة ، وكذلك عنصر بداية الحلقة.

Answer 9

أفضل إجابة وجدتها كانت هنا:
Tianrunhe: قائمة الإنتاج المرتبطة بالدولة

• "M" يجري المسافة بين الرأس و START_LOOP
• "ل" طول الحلقة
• "D" يجري المسافة بين Meeting_Point و START_LOOP

• P1 يتحرك في V ، و P2 يتحرك في 2*V

  عندما تلتقي المؤشرتين: تشغيل المسافة هو = m+ n*l -d = 2*(m+ l -d)

  => وهذا يعني (غير رياضي يظهر هنا) أنه إذا بدأ P1 من Head & P2 يبدأ من Meeting_point وينتقلون بنفس السرعة ، فسوف يجتمعون @ start_loop

Answer 10

تشير إلى هذه رابط للإجابة الشاملة.

Answer 11

1. تابع بالطريقة المعتادة التي ستستخدمها للعثور على الحلقة. بمعنى آخر. لديك مؤشران ، زيادة واحدة في خطوة واحدة وغيرها في خطوتين ، إذا التقى كلاهما في وقت ما ، هناك حلقة.

2. احتفظ بأحد المؤشرات الثابتة ، احصل على إجمالي عدد العقد في الحلقة Say L.

3. الآن من هذه النقطة (زيادة المؤشر الثاني إلى العقدة التالية في الحلقة) في الحلقة عكس القائمة المرتبطة وحساب عدد العقد التي تم اجتيازها ، على سبيل المثال.

4. الآن باستخدام المؤشر الثاني (حلقة مكسورة) من نفس النقطة في حلقة travrse القائمة المرتبطة وحساب عدد العقد المتبقية يقول y

5. تبدأ الحلقة بعد العقد ((x+y) -l) 2. أو يبدأ في (((x+y) -l) 2+1) th node.

Answer 12

1. تابع بالطريقة المعتادة التي ستستخدمها للعثور على الحلقة. بمعنى آخر. لديك مؤشران ، زيادة واحدة في خطوة واحدة وغيرها في خطوتين ، إذا التقى كلاهما في وقت ما ، هناك حلقة.

2. احتفظ بأحد المؤشرات الثابتة ، احصل على إجمالي عدد العقد في الحلقة Say L.

3. الآن من هذه النقطة (زيادة المؤشر الثاني إلى العقدة التالية في الحلقة) في الحلقة عكس القائمة المرتبطة وحساب عدد العقد التي تم اجتيازها ، على سبيل المثال.

4. الآن باستخدام المؤشر الثاني (حلقة مكسورة) من نفس النقطة في حلقة travrse القائمة المرتبطة وحساب عدد العقد المتبقية يقول y

5. تبدأ الحلقة بعد العقد ((x+y) -l) 2. أو يبدأ في (((x+y) -l) 2+1) th node.

Answer 13

void loopstartpoint(Node head){
    Node slow = head.next;;
    Node fast = head.next.next;

    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;

        if(slow==fast){
            System.out.println("Detected loop ");
            break;
        }
    }

    slow=head;
    while(slow!=fast){
        slow= slow.next;
        fast = fast.next;
    }
    System.out.println("Starting position of loop is "+slow.data);
}

Answer 14

1. اكتشف حلقة
2. انسخ عنوان كل عنصر إلى مجموعة. إذا تم العثور على تكرار ، فهذه بداية الحلقة