Linked List

Box-এর একটা chain, যেখানে প্রতিটা box শুধু পরেরটাকে চেনে।

মূল ধারণা

Linked list অনেকটা treasure hunt-এর মতো: প্রতিটা clue (node)-এ একটা value থাকে আর বলা থাকে পরের clue কোথায়। সরাসরি 5 নম্বর clue-তে যাওয়া যায় না; শুরু থেকে chain ধরে এগোতে হয়। শেষ clue-টা nil (কিছু নেই) দেখায়।

Reverse করা মানে প্রতিটা arrow উল্টে দেওয়া। এজন্য তিনটা helper লাগে: prev (যে অংশ reverse হয়ে গেছে), curr (যে node এখন ঠিক করা হচ্ছে) আর next (আগে থেকে save করা, যাতে arrow উল্টানোর পর বাকি chain হারিয়ে না যায়)।

Cycle detection: একটা ট্র্যাকে দুজন দৌড়বিদ, একজন অন্যজনের দ্বিগুণ জোরে। ট্র্যাক গোলাকার (loop) হলে দ্রুতজন একসময় ধীরজনকে এক চক্কর ছাড়িয়ে যায় আর তারা মিলে যায়। ট্র্যাক সোজা হলে দ্রুতজন শুধু শেষ প্রান্ত দিয়ে বেরিয়ে যায়।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity

Reverse: O(n) time complexity, O(1) space complexity – একবার pass, তিনটা pointer। Cycle detection: O(n) time complexity, O(1) space complexity – hash-set দিয়ে করলে লাগে O(n) space complexity, সেটার সাথে তুলনা করুন।