C++ এ একটি লিঙ্ক করা তালিকায় একটি লুপ সনাক্ত করুন

একটি লিঙ্ক করা তালিকার শেষ নোড যেখানে একটি লুপ রয়েছে সেটি NULL এর পরিবর্তে একই তালিকার অন্য নোডকে নির্দেশ করবে৷ যদি একটি লিঙ্কযুক্ত তালিকায় একটি নোড থাকে যা পরবর্তী পয়েন্টার অনুসরণ করে বারবার অ্যাক্সেস করা যেতে পারে তবে তালিকাটিকে বলা হয় একটি চক্র আছে

সাধারণত, লিঙ্ক করা তালিকার শেষ নোডটি তালিকার উপসংহার বোঝাতে একটি NULL রেফারেন্সকে বোঝায়। যাইহোক, একটি লুপ সহ লিঙ্কযুক্ত তালিকায়, তালিকার শেষ নোডটি একটি স্টার্ট নোড, একটি অভ্যন্তরীণ নোড বা নিজেই বোঝায়। অতএব, এই ধরনের পরিস্থিতিতে, আমাদের অবশ্যই NULL-তে পরবর্তী নোডের রেফারেন্স সেট করে লুপটি সনাক্ত করতে হবে এবং শেষ করতে হবে। লিঙ্ক করা তালিকায় লুপের সনাক্তকরণ অংশটি এই নিবন্ধে ব্যাখ্যা করা হয়েছে।

C++ এ, লিঙ্ক করা তালিকায় লুপ খোঁজার অনেক উপায় রয়েছে:

হ্যাশ টেবিল-ভিত্তিক পদ্ধতি : এই পদ্ধতি একটি হ্যাশ টেবিলে পরিদর্শন করা নোডের ঠিকানা সংরক্ষণ করে। লিঙ্ক করা তালিকায় একটি লুপ বিদ্যমান থাকে যদি একটি নোড আগে থেকেই হ্যাশ টেবিলে উপস্থিত থাকে যখন এটি আবার পরিদর্শন করা হয়।

ফ্লয়েডের চক্র পদ্ধতি : 'কচ্ছপ এবং খরগোশ' অ্যালগরিদম, সাধারণত ফ্লয়েডের সাইকেল-ফাইন্ডিং অ্যালগরিদম নামে পরিচিত: এই কৌশলটি দুটি পয়েন্টার ব্যবহার করে, একটি অন্যটির চেয়ে ধীরে ধীরে এবং অন্যটি আরও দ্রুত চলে। দ্রুত পয়েন্টারটি শেষ পর্যন্ত ধীর পয়েন্টারকে ছাড়িয়ে যাবে যদি লিঙ্ক করা তালিকায় একটি লুপ থাকে, লুপের অস্তিত্ব প্রকাশ করে।

পুনরাবৃত্ত পদ্ধতি : এই পদ্ধতিটি বারবার নিজেকে কল করে লিঙ্ক করা তালিকার মধ্য দিয়ে যায়। বর্তমান নোডটি পূর্বে পরিদর্শন করা থাকলে লিঙ্ক করা তালিকায় একটি লুপ থাকে।

স্ট্যাক-ভিত্তিক পদ্ধতি : এই পদ্ধতি একটি স্ট্যাকের মধ্যে পরিদর্শন করা নোডের ঠিকানা সংরক্ষণ করে। লিঙ্ক করা তালিকায় একটি লুপ উপস্থিত থাকে যদি স্ট্যাকের মধ্যে একটি নোড ইতিমধ্যেই থাকে যখন এটি আবার পরিদর্শন করা হয়।

ধারণাটি বোঝার জন্য প্রতিটি পদ্ধতির বিস্তারিত ব্যাখ্যা করা যাক।

অ্যাপ্রোচ 1: হ্যাশসেট অ্যাপ্রোচ

হ্যাশিং ব্যবহার করা সবচেয়ে সহজবোধ্য পদ্ধতি। এখানে, আমরা নোড ঠিকানাগুলির সাথে একটি হ্যাশ টেবিল রাখার সময় একের পর এক তালিকার মধ্য দিয়ে যাই। অতএব, একটি লুপ বিদ্যমান যদি আমরা কখনও বর্তমান নোডের পরবর্তী ঠিকানা জুড়ে যাই যা ইতিমধ্যে হ্যাশ টেবিলে রয়েছে। অন্যথায়, লিংকড লিস্টে কোন লুপ থাকবে না যদি আমরা NULL এ চলে যাই (অর্থাৎ, লিংকড লিস্টের শেষে পৌঁছাই)।

এই কৌশল বাস্তবায়ন করা বেশ সহজ হবে।

লিঙ্ক করা তালিকাটি অতিক্রম করার সময়, আমরা একটি unordered_hashmap ব্যবহার করব এবং এতে নোড যোগ করতে থাকব।

এখন, একবার আমরা একটি নোড দেখতে পাব যা ইতিমধ্যেই মানচিত্রে দেখানো হয়েছে, আমরা জানব যে আমরা লুপের শুরুতে পৌঁছেছি।

• • উপরন্তু, আমরা প্রতিটি ধাপে দুটি পয়েন্টার রেখেছি, হেডনোড বর্তমান নোড নির্দেশ করে এবং lastNode পুনরাবৃত্তি করার সময় বর্তমান নোডের পূর্ববর্তী নোডের দিকে নির্দেশ করে।
  • আমাদের হিসাবে হেডনোড এখন লুপের স্টার্ট নোডের দিকে নির্দেশ করছে এবং হিসাবে lastNode নোডের দিকে নির্দেশ করছিল কোন মাথার দিকে নির্দেশ করছে (অর্থাৎ, এটি উল্লেখ করছে lastNode লুপের), আমাদের হেডনোড বর্তমানে লুপের স্টার্ট নোডের দিকে নির্দেশ করছে।
  • l সেট করে লুপটি ভেঙে যাবে astNode->next == NULL .

এটি করার মাধ্যমে, লুপের প্রাথমিক নোডকে উল্লেখ করার পরিবর্তে শেষ লুপ নোডটি NULL-এর দিকে নির্দেশ করা শুরু করে।

হ্যাশিং পদ্ধতির গড় সময় এবং স্থান জটিলতা হল O(n)। পাঠককে সর্বদা সচেতন থাকতে হবে যে প্রোগ্রামিং ভাষায় বিল্ট-ইন হ্যাশিং ডেটাস্ট্রাকচারের বাস্তবায়ন হ্যাশিং-এ সংঘর্ষের ক্ষেত্রে মোট সময় জটিলতা নির্ধারণ করবে।

উপরের পদ্ধতির জন্য C++ প্রোগ্রাম বাস্তবায়ন (হ্যাশসেট):

আউটপুট:

কোডের ধাপে ধাপে ব্যাখ্যা নিচে দেওয়া হল:

1. 1. bits/stdc++.h> শিরোনাম ফাইল, যেটিতে সাধারণ C++ লাইব্রেরি রয়েছে, কোডটিতে অন্তর্ভুক্ত করা হয়েছে।
   2. 'নোড' নামে একটি কাঠামো তৈরি করা হয়েছে, এবং এতে দুটি সদস্য রয়েছে: তালিকার পরবর্তী নোডের একটি রেফারেন্স এবং 'মান' নামক একটি পূর্ণসংখ্যা।
   3. ইনপুট হিসাবে একটি পূর্ণসংখ্যা মান এবং 'পরবর্তী' পয়েন্টার NULL এ সেট করা হলে, 'newNode' ফাংশনটি সেই মান সহ একটি নতুন নোড তৈরি করে।
   4. কাজ ' ফাংশন হ্যাশম্যাপ' সংজ্ঞায়িত করা হয়েছে, যা ইনপুট হিসাবে লিঙ্ক তালিকার প্রধান নোডে একটি পয়েন্টার নেয়।
   5. ভিতরে ' ফাংশন হ্যাশম্যাপ ' ফাংশন, 'হ্যাশ_ম্যাপ' নামে একটি অ-অর্ডারড_ম্যাপ তৈরি করা হয়, যা একটি হ্যাশ ম্যাপ ডেটা স্ট্রাকচার বাস্তবায়ন করতে ব্যবহৃত হয়।
   6. তালিকার শেষ নোডের একটি পয়েন্টার NULL তে আরম্ভ করা হয়েছে।
   7. একটি while লুপ লিঙ্ক করা তালিকা অতিক্রম করতে ব্যবহৃত হয়, যা হেড নোড থেকে শুরু হয় এবং হেড নোড NULL না হওয়া পর্যন্ত চলতে থাকে।
   8. যদি হ্যাশ ম্যাপে বর্তমান নোড (হেডনোড) ইতিমধ্যে উপস্থিত না থাকে তবে লাস্টনোড পয়েন্টারটি while লুপের ভিতরে বর্তমান নোডে আপডেট করা হয়।
   9. যদি বর্তমান নোডটি মানচিত্রে পাওয়া যায়, তাহলে এর অর্থ হল লিঙ্ক করা তালিকায় একটি লুপ উপস্থিত রয়েছে। লুপ মুছে ফেলার জন্য, পরবর্তী পয়েন্টার lastNode তৈরি খালি এবং যখন লুপ ভাঙ্গা হয়.
   10. লিঙ্ক করা তালিকার হেড নোডটি 'ডিসপ্লে' নামক একটি ফাংশনের জন্য ইনপুট হিসাবে ব্যবহৃত হয়, যা তালিকার প্রতিটি নোডের মান শুরু থেকে শেষ পর্যন্ত আউটপুট করে।
   11. মধ্যে প্রধান ফাংশন, একটি লুপ তৈরি।
   12. 'ফাংশন হ্যাশম্যাপ' ফাংশনটিকে হেডনোড পয়েন্টার দিয়ে ইনপুট হিসাবে ডাকা হয়, যা তালিকা থেকে লুপটি সরিয়ে দেয়।
   13. পরিবর্তিত তালিকাটি 'ডিসপ্লে' ফাংশন ব্যবহার করে প্রদর্শিত হয়।

পদ্ধতি 2: ফ্লয়েডস সাইকেল

ফ্লয়েডের সাইকেল ডিটেকশন অ্যালগরিদম, যা প্রায়ই কচ্ছপ এবং খরগোশ অ্যালগরিদম নামে পরিচিত, একটি লিঙ্ক করা তালিকায় চক্রগুলি সনাক্ত করার এই পদ্ধতির ভিত্তি প্রদান করে। 'ধীর' পয়েন্টার এবং 'দ্রুত' পয়েন্টার, যা বিভিন্ন গতিতে তালিকা অতিক্রম করে, এই কৌশলটিতে ব্যবহৃত দুটি পয়েন্টার। দ্রুত পয়েন্টার দুই ধাপ অগ্রসর হয় যেখানে ধীর পয়েন্টার প্রতি পুনরাবৃত্তিতে এক ধাপ অগ্রসর হয়। দুটি পয়েন্ট মুখোমুখি হলে লিঙ্ক করা তালিকায় একটি চক্র বিদ্যমান থাকে।

1. লিঙ্ক করা তালিকার হেড নোডের সাথে, আমরা দ্রুত এবং ধীর নামে দুটি পয়েন্টার শুরু করি।

2. এখন আমরা লিঙ্ক করা তালিকার মধ্য দিয়ে যাওয়ার জন্য একটি লুপ চালাই। দ্রুত পয়েন্টারটিকে প্রতিটি পুনরাবৃত্তির ধাপে ধীর পয়েন্টারের সামনে দুটি স্থানে সরানো উচিত।

3. যদি দ্রুত পয়েন্টার তালিকার শেষে পৌঁছে যায় তবে লিঙ্ক করা তালিকায় একটি লুপ থাকবে না (fastPointer == NULL বা fastPointer->পরবর্তী == NULL)। যদি না হয়, দ্রুত এবং ধীর পয়েন্টার শেষ পর্যন্ত মিলিত হবে, যার মানে লিঙ্ক করা তালিকার একটি লুপ আছে।

উপরের পদ্ধতির জন্য C++ প্রোগ্রাম বাস্তবায়ন (ফ্লয়েডস সাইকেল):

আউটপুট:

ব্যাখ্যা:

1. 1. প্রাসঙ্গিক হেডার, যেমন 'bits/stdc++.h' এবং 'std::cout,' প্রথমে অন্তর্ভুক্ত করা হয়েছে।
   2. 'নোড' কাঠামো, যা লিঙ্ক করা তালিকার একটি নোডের জন্য দাঁড়ায়, তারপর ঘোষণা করা হয়। একটি পরবর্তী পয়েন্টার যা তালিকায় নিম্নলিখিত নোডের দিকে নিয়ে যায় প্রতিটি নোডে একটি পূর্ণসংখ্যা ডেটা ক্ষেত্রের সাথে অন্তর্ভুক্ত করা হয়।
   3. তারপর, এটি 'deleteLoop' এবং 'detectAndDeleteLoop,' দুটি ফাংশন সংজ্ঞায়িত করে। প্রথম পদ্ধতি ব্যবহার করে একটি লিঙ্কযুক্ত তালিকা থেকে একটি লুপ সরানো হয়, এবং দ্বিতীয় ফাংশন ব্যবহার করে তালিকায় একটি লুপ সনাক্ত করা হয়, যা লুপটি সরানোর জন্য প্রথম পদ্ধতিটিকে কল করে।
   4. প্রধান ফাংশনে পাঁচটি নোড সহ একটি নতুন লিঙ্কযুক্ত তালিকা তৈরি করা হয় এবং শেষ নোডের পরবর্তী পয়েন্টারটি তৃতীয় নোডে সেট করে একটি লুপ স্থাপন করা হয়।
   5. এটি তারপর একটি আর্গুমেন্ট হিসাবে লিঙ্ক করা তালিকার প্রধান নোড পাস করার সময় 'detectAndDeleteLoop' পদ্ধতিতে একটি কল করে। লুপ সনাক্ত করতে, এই ফাংশনটি 'ধীর এবং দ্রুত পয়েন্টার' পদ্ধতি ব্যবহার করে। এটি দুটি পয়েন্টার নিয়োগ করে যা তালিকার শীর্ষে শুরু হয়, স্লোপিটিআর এবং ফাস্টপিটিআর। যখন দ্রুত পয়েন্টার একবারে দুটি নোড সরায়, তখন ধীর পয়েন্টারটি একবারে একটি নোড সরায়। তালিকায় একটি লুপ থাকলে দ্রুত পয়েন্টার শেষ পর্যন্ত ধীরগতির পয়েন্টারকে ছাড়িয়ে যাবে এবং দুটি পয়েন্ট একই নোডে সংঘর্ষ করবে।
   6. ফাংশনটি 'deleteLoop' ফাংশনকে আহ্বান করে যদি এটি একটি লুপ খুঁজে পায়, তালিকার প্রধান নোড এবং ইনপুট হিসাবে ধীর এবং দ্রুত পয়েন্টারগুলির সংযোগস্থল সরবরাহ করে। এই পদ্ধতিটি তালিকার প্রধান নোডে দুটি পয়েন্টার, ptr1 এবং ptr2 স্থাপন করে এবং লুপে নোডের সংখ্যা গণনা করে। এটি অনুসরণ করে, এটি একটি পয়েন্টার k নোডকে অগ্রসর করে, যেখানে k হল লুপের মোট নোডের সংখ্যা। তারপর, যতক্ষণ না তারা লুপের শুরুতে মিলিত হয়, এটি একটি সময়ে উভয় পয়েন্ট এক নোডকে অগ্রসর করে। লুপের শেষে নোডের পরবর্তী পয়েন্টারটিকে NULL এ সেট করে লুপটি ভেঙে ফেলা হয়।
   7. লুপ অপসারণের পরে, এটি একটি চূড়ান্ত পদক্ষেপ হিসাবে লিঙ্ক তালিকা প্রদর্শন করে।

পদ্ধতি 3: পুনরাবৃত্তি

Recursion হল সমস্যাগুলিকে ছোট, সহজ উপ-সমস্যাগুলিতে ভাগ করে সমাধান করার একটি কৌশল। তালিকার শেষ না হওয়া পর্যন্ত তালিকার পরবর্তী নোডের জন্য ক্রমাগত একটি ফাংশন চালানোর মাধ্যমে একটি লুপ পাওয়া গেলে একটি একক লিঙ্কযুক্ত তালিকা অতিক্রম করতে পুনরাবৃত্তি ব্যবহার করা যেতে পারে।

একটি এককভাবে লিঙ্কযুক্ত তালিকায়, লুপ খুঁজে বের করার জন্য পুনরাবৃত্তি ব্যবহার করার পিছনে মূল নীতি হল তালিকার মাথা থেকে শুরু করা, বর্তমান নোডটিকে প্রতিটি ধাপে ভিজিট করা হিসাবে চিহ্নিত করা এবং তারপরে ফাংশনটি পুনরাবৃত্তি করে পরবর্তী নোডে যেতে যে নোড. পদ্ধতিটি সম্পূর্ণ লিঙ্কযুক্ত তালিকার উপর পুনরাবৃত্তি করবে কারণ এটি পুনরাবৃত্তিমূলকভাবে বলা হয়।

তালিকায় একটি লুপ থাকে যদি একটি নোড যা পূর্বে পরিদর্শন হিসাবে চিহ্নিত করা হয়েছে ফাংশন দ্বারা সম্মুখীন হয়; এই ক্ষেত্রে, ফাংশন সত্য ফিরে আসতে পারে. পদ্ধতিটি মিথ্যা ফিরে আসতে পারে যদি এটি একটি পরিদর্শন করা নোড জুড়ে না চালিয়ে তালিকার শেষে পৌঁছায়, যা নির্দেশ করে যে কোনও লুপ নেই।

যদিও একটি একক লিঙ্কযুক্ত তালিকায় একটি লুপ খুঁজে বের করার জন্য পুনরাবৃত্তি ব্যবহার করার এই কৌশলটি ব্যবহার এবং বোঝার জন্য সহজ, এটি সময় এবং স্থান জটিলতার পরিপ্রেক্ষিতে সবচেয়ে কার্যকর নাও হতে পারে।

উপরের পদ্ধতির জন্য C++ প্রোগ্রাম বাস্তবায়ন (পুনরাবৃত্তি):

আউটপুট:

ব্যাখ্যা:

1. 1. কাজ LoopLinkedList detect() এই প্রোগ্রামে একটি ইনপুট হিসাবে লিঙ্ক তালিকার প্রধান গ্রহণ করে।
   2. লিঙ্ক করা তালিকা জুড়ে পুনরাবৃত্তি করার জন্য ফাংশন দ্বারা পুনরাবৃত্তি ব্যবহার করা হয়। পুনরাবৃত্তের জন্য মৌলিক ক্ষেত্রে, এটি বর্তমান নোডটি NULL কিনা তা নির্ধারণ করে শুরু হয়। যদি তাই হয়, পদ্ধতিটি মিথ্যা ফেরত দেয়, নির্দেশ করে যে কোন লুপ বিদ্যমান নেই।
   3. বর্তমান নোডের 'পরিদর্শন করা' সম্পত্তির মান তারপরে এটি আগে পরিদর্শন করা হয়েছে কিনা তা পরীক্ষা করা হয়। এটি পরিদর্শন করা হলে এটি সত্য ফিরে আসে, একটি লুপ পাওয়া গেছে বলে পরামর্শ দেয়।
   4. ফাংশনটি বর্তমান নোডটিকে পরিদর্শন করা হিসাবে চিহ্নিত করে যদি এটি ইতিমধ্যেই পরিদর্শন করা হয়ে থাকে তবে তার 'পরিদর্শন করা' বৈশিষ্ট্যটিকে সত্যে পরিবর্তন করে।
   5. পরিদর্শন করা ভেরিয়েবলের মান তারপর বর্তমান নোডটি আগে পরিদর্শন করা হয়েছে কিনা তা দেখতে পরীক্ষা করা হয়। এটি আগে ব্যবহার করা হলে, একটি লুপ বিদ্যমান থাকা আবশ্যক, এবং ফাংশন সত্য ফেরত.
   6. অবশেষে, ফাংশন পাস করে তালিকার পরবর্তী নোডের সাথে নিজেকে কল করে headNode->পরবর্তী একটি যুক্তি হিসাবে। পুনরাবৃত্তিমূলকভাবে , এটি করা হয় যতক্ষণ না হয় একটি লুপ পাওয়া যায় বা সমস্ত নোড পরিদর্শন করা হয়। মানে, ফাংশনটি ভিজিট করা ভেরিয়েবলটিকে সত্যে সেট করে যদি বর্তমান নোডটি লিঙ্ক করা তালিকার নিম্নলিখিত নোডের জন্য বারবার কল করার আগে কখনও পরিদর্শন করা না হয়।
   7. কোড তিনটি নোড তৈরি করে এবং একটি লিঙ্ক তালিকা তৈরি করতে তাদের সাথে যোগ দেয় প্রধান ফাংশন . পদ্ধতি LoopLinkedList detect() তারপর তালিকার প্রধান নোডে আহ্বান করা হয়। প্রোগ্রাম উত্পাদন করে ' লিঙ্ক করা তালিকায় লুপ কাটা হয়েছে 'যদি LoopLinkedList detect() সত্য ফেরত; অন্যথায়, এটি আউটপুট ' লিঙ্ক করা তালিকায় কোনো লুপ সনাক্ত করা যায়নি '
   8. কোডটি তারপর দ্বিতীয় নোডে শেষ নোডের পরবর্তী পয়েন্টার সেট করে লিঙ্কযুক্ত তালিকায় একটি লুপ সন্নিবেশ করে। তারপর, ফাংশনের ফলাফলের উপর নির্ভর করে, এটি চলে LoopLinkedList detect() আবার এবং হয় উত্পাদন করে ' লিঙ্ক করা তালিকায় লুপ কাটা হয়েছে 'বা' লিঙ্ক করা তালিকায় কোনো লুপ সনাক্ত করা যায়নি '

পদ্ধতি 4: স্ট্যাক ব্যবহার করা

একটি লিঙ্ক করা তালিকার লুপগুলি একটি স্ট্যাক এবং 'ডেপথ-ফার্স্ট সার্চ' (DFS) পদ্ধতি ব্যবহার করে পাওয়া যেতে পারে। মৌলিক ধারণাটি লিঙ্কযুক্ত তালিকার মাধ্যমে পুনরাবৃত্তি করা, প্রতিটি নোডকে স্ট্যাকের দিকে ঠেলে দেওয়া যদি এটি ইতিমধ্যেই পরিদর্শন না করে থাকে। একটি লুপ স্বীকৃত হয় যদি একটি নোড যা ইতিমধ্যে স্ট্যাকের মধ্যে আছে আবার সম্মুখীন হয়।

এখানে পদ্ধতির একটি সংক্ষিপ্ত বিবরণ রয়েছে:

1. 1. পরিদর্শন করা নোডগুলি রেকর্ড করতে একটি খালি স্ট্যাক এবং একটি ভেরিয়েবল তৈরি করুন।
   2. লিঙ্ক করা তালিকাটিকে স্ট্যাকের উপরে পুশ করুন, শীর্ষ থেকে শুরু করুন। একটি নোট করুন যে মাথা পরিদর্শন করা হয়েছে।
   3. তালিকার পরবর্তী নোডটিকে স্ট্যাকের উপর চাপুন। এই নোডে একটি পরিদর্শন চিহ্ন যোগ করুন।
   4. আপনি তালিকাটি অতিক্রম করার সাথে সাথে, প্রতিটি নতুন নোডকে স্ট্যাকের উপর চাপুন যে এটি পরিদর্শন করা হয়েছে।
   5. পূর্বে পরিদর্শন করা একটি নোড স্ট্যাকের শীর্ষে আছে কিনা তা দেখতে পরীক্ষা করুন যদি এটি সম্মুখীন হয়। যদি তাই হয়, একটি লুপ পাওয়া গেছে, এবং লুপটি স্ট্যাকের নোড দ্বারা চিহ্নিত করা হয়।
   6. স্ট্যাকের বাইরে নোডগুলি পপ করুন এবং কোনও লুপ না পাওয়া গেলে তালিকাটি অতিক্রম করতে থাকুন।

উপরের পদ্ধতির জন্য C++ প্রোগ্রাম বাস্তবায়ন (স্ট্যাক)

আউটপুট:

ব্যাখ্যা:

এই প্রোগ্রামটি একটি স্ট্যাক ব্যবহার করে খুঁজে বের করে যে একটি এককভাবে লিঙ্ক করা তালিকায় একটি লুপ আছে কিনা।

• 1. ইনপুট/আউটপুট স্ট্রীম লাইব্রেরি এবং স্ট্যাক লাইব্রেরি উভয়ই প্রথম লাইনে উপস্থিত।

  2. স্ট্যান্ডার্ড নেমস্পেসটি দ্বিতীয় লাইনে অন্তর্ভুক্ত করা হয়েছে, যা আমাদের ইনপুট/আউটপুট স্ট্রীম লাইব্রেরির ফাংশনগুলিকে 'std::' দিয়ে উপসর্গ না করেই অ্যাক্সেস করতে দেয়।

  3. নিম্নলিখিত লাইনটি স্ট্রাকট নোডকে সংজ্ঞায়িত করে, যা দুটি সদস্য নিয়ে গঠিত: 'ডেটা' নামে একটি পূর্ণসংখ্যা এবং 'পরবর্তী' নামক আরেকটি নোডের একটি পয়েন্টার।

  4. লিঙ্ক করা তালিকার মাথাটি মেথড detectLoopLinkedList() এর জন্য একটি ইনপুট, যা পরবর্তী লাইনে সংজ্ঞায়িত করা হয়েছে। ফাংশনটি একটি বুলিয়ান মান তৈরি করে যা নির্দেশ করে যে একটি লুপ পাওয়া গেছে কিনা।

  5. 'স্ট্যাক' নামক নোড পয়েন্টারগুলির একটি স্ট্যাক এবং 'tempNode' নামের একটি নোডের একটি পয়েন্টার যা headNode-এর মান দিয়ে শুরু করা হয় উভয়ই ফাংশনের ভিতরে তৈরি করা হয়।

  6. তারপর, যতক্ষণ tempNode একটি নাল পয়েন্টার না হয়, আমরা একটি while loop এ প্রবেশ করি।

  (a) স্ট্যাকের উপরের উপাদানটি অবশ্যই বর্তমান নোডের সাথে মিলবে যাতে আমরা নির্ধারণ করতে পারি যে এটি খালি নয়। আমরা সত্য ফিরে যদি এই ক্ষেত্রে হয় কারণ একটি লুপ পাওয়া গেছে.

  (b) যদি পূর্বোক্ত শর্তটি মিথ্যা হয়, তাহলে বর্তমান নোড পয়েন্টারটিকে স্ট্যাকের উপর ঠেলে দেওয়া হয় এবং tempNode লিঙ্ক করা তালিকার নিম্নলিখিত নোডে সেট করা হয়।

  7. while লুপের পরে আমরা মিথ্যা রিটার্ন করি কারণ কোন লুপ দেখা যায়নি।

  8. আমরা তিনটি নোড অবজেক্ট তৈরি করি এবং সেগুলিকে main() ফাংশনে ইনিশিয়ালাইজ করি। যেহেতু প্রথম উদাহরণে কোনও লুপ নেই, তাই আমরা প্রতিটি নোডের 'পরবর্তী' পয়েন্টারগুলি সঠিকভাবে সেট করি।

উপসংহার:

উপসংহারে, একটি লিঙ্ক করা তালিকায় লুপ সনাক্ত করার সর্বোত্তম পদ্ধতিটি নির্দিষ্ট ব্যবহারের ক্ষেত্রে এবং সমস্যার সীমাবদ্ধতার উপর নির্ভর করে। হ্যাশ টেবিল এবং ফ্লয়েডের সাইকেল-ফাইন্ডিং অ্যালগরিদম হল দক্ষ পদ্ধতি এবং এগুলি অনুশীলনে ব্যাপকভাবে ব্যবহৃত হয়। স্ট্যাক এবং পুনরাবৃত্তি কম কার্যকর পদ্ধতি কিন্তু তারা আরও স্বজ্ঞাত।