هذا سؤال اختبار مكتوب كلاسيكي من Microsoft. يجتاز المؤشران h1 وh2 القائمة المرتبطة بشكل فردي من البداية، ويتحرك h1 للأمام خطوة واحدة في كل مرة، ويتحرك h2 للأمام خطوتين في كل مرة الحلقة غير موجودة؛ إذا لامس h2 h1 الذي يجب أن يكون خلفه، فهذا يعني وجود حلقة (أي حدوث حلقة).
إذا كانت الحلقة غير موجودة، فيجب أن يواجه h2 القيمة NULL أولاً:
إذا كانت الحلقة موجودة، فمن المؤكد أن h2 وh1 سيلتقيان، وتكون نقطة الالتقاء داخل الحلقة: تعبر h2 بشكل أسرع من h1، وبالتأكيد لن تلتقي في بداية القائمة المرتبطة غير الحلقية، لذا عندما يدخل كل من h1 وh2 الحلقة أخيرًا، كل حركة لـ h2 ستقلل الفجوة بين h2 وh1 في الاتجاه الأمامي بمقدار 1. أخيرًا، سيتم تقليل الفجوة بين h1 وh2 إلى 0، أي أنهما يلتقيان.
الفراغ الثابت العام الرئيسي(String args[]){
قائمة SingleList = New SingleList();
ل(int i=0;i<100;i++){
list.add(i);
}
System.out.print(SingleList.isExistingLoop(list));
}
}
العقدة العامة (قيمة الكائن) {
this.data = value;
}
العقدة العامة (){
this.data = null;
this.next = null;
}
}
الحرف الأول باطلة خاصة () {
this.size = 0;
this.head = new Node();
}
القائمة المنفردة العامة (){
الحرف الأول () ؛
}
تحتوي القيمة المنطقية العامة على (قيمة الكائن) {
علامة منطقية = خطأ؛
Node p = head.next;
بينما(ع!=فارغة){
إذا(value.equals(p.data)){
العلم = صحيح؛
استراحة؛
}آخر(
ع = ص.next;
)
}
علم العودة؛
}
إضافة منطقية عامة (قيمة الكائن) {
إذا (يحتوي على (القيمة))
عودة كاذبة.
آخر{
العقدة p = العقدة الجديدة(القيمة);
p.next=head.next;
head.next = p;
الحجم++;
}
عودة صحيحة؛
}
}