লিংকড লিস্টপড়তে ৫ মিনিট লাগবে

রিভার্সিং লিংকড লিস্ট (Reversing a Linked List)

পুরো শেকলটাকে ধরে উল্টে দেওয়া — যাতে শেষের কড়া হয়ে যায় প্রথম কড়া
time: O(n)space: O(1) (লুপের জন্য) / O(n) (রিকার্শনের জন্য)

ধরুন গুপ্তধন খোঁজার একটা ম্যাপ: ক্লু ১ → ক্লু ২ → ক্লু ৩ → গুপ্তধন। এবার এটাকে পুরোপুরি উল্টে দিন: গুপ্তধন → ক্লু ৩ → ক্লু ২ → ক্লু ১। অর্থাৎ, যে তীর চিহ্নগুলো আগে সামনের দিকে নির্দেশ করত, সেগুলো এখন পেছনের দিকে পয়েন্ট করছে। আর একদম শেষের নোডটা হয়ে গেছে নতুন হেড (head) বা শুরুর মাথা।

একটা লিংকড লিস্টকে উল্টে দেওয়া (reverse করা) হলো এই ডেটা স্ট্রাকচারের সবচেয়ে মৌলিক বা বেসিক একটা কাজ। ইন্টারভিউতে এটা খুব ফেমাস একটা প্রশ্ন, কারণ এটা দিয়ে যাচাই করা হয় আপনি পয়েন্টারের (pointer) খেলাটা ঠিকমতো বোঝেন কি না। খুশির খবর হলো: কাজটা দেখতে যতটা কঠিন মনে হয়, আসলে ততটা না।

ইটারেটিভ পদ্ধতি (লুপ চালিয়ে)

লিস্টের শুরু থেকে শেষ পর্যন্ত একবার হেঁটে যান, আর যানয়ার পথে প্রতিটা পয়েন্টারের ডিরেকশন উল্টে দিন। এর জন্য আপনার শুধু তিনটা ভেরিয়েবল লাগবে:

  • prev — একটু আগে যে নোডের কাজ শেষ করেছেন (শুরুতে এটা null থাকে)
  • curr — বর্তমানে যে নোডে দাঁড়িয়ে আছেন (শুরুতে এটা head থাকে)
  • next — curr.next-কে চেঞ্জ করার আগে সেটাকে সেভ করে রাখার একটা টেম্পোরারি বা অস্থায়ী জায়গা

প্রতিটা পদক্ষেপে আপনাকে যা করতে হবে:

  1. next = curr.next লিখে সামনের নোডের ঠিকানাটা সেভ করুন (তা না হলে লিস্টের বাকি অংশ হারিয়ে যাবে)।
  2. পয়েন্টার উল্টে দিন: curr.next = prev (অর্থাৎ, সামনের দিকে না তাকিয়ে এখন পেছনের দিকে তাকাও)।
  3. এক ধাপ সামনে এগোন: prev = curr, curr = next।

যখন curr-এর মান null বা ফাঁকা হয়ে যাবে, তার মানে সব নোডের কাজ শেষ। তখন prev-ই হবে আপনার রিভার্স করা লিস্টের একদম নতুন হেড (head)।

◈ Watch list reversal

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

দ্রষ্টব্য: সবচেয়ে কমন ভুলটা হলো: curr.next-কে উল্টে দেওয়ার আগে সেটার ঠিকানা next = curr.next লিখে সেভ করতে ভুলে যানয়া। একবার curr.next = prev লিখে পয়েন্টার ঘুরিয়ে দিলে, লিস্টের বাকি অংশের সাথে আপনার যোগসূত্র একদম চিরতরে বিচ্ছিন্ন হয়ে যাবে। তাই পয়েন্টার ঘোরানোর আগে সবসময় সামনের ঠিকানাটা সেভ করে রাখবেন।

উদাহরণের সাহায্যে দেখি

ধরি লিস্টটা হলো: ১ → ২ → ৩ → ৪ → null

প্রাথমিক অবস্থা: prev = null, curr = ১

  • ধাপ ১: next=২ সেভ করি, পয়েন্টার উল্টাই ১→null, এক ধাপ এগোই। বর্তমান অবস্থা: prev=১, curr=২
  • ধাপ ২: next=৩ সেভ করি, পয়েন্টার উল্টাই ২→১, এক ধাপ এগোই। বর্তমান অবস্থা: prev=২, curr=৩
  • ধাপ ৩: next=৪ সেভ করি, পয়েন্টার উল্টাই ৩→২, এক ধাপ এগোই। বর্তমান অবস্থা: prev=৩, curr=৪
  • ধাপ ৪: next=null সেভ করি, পয়েন্টার উল্টাই ৪→৩, এক ধাপ এগোই। বর্তমান অবস্থা: prev=৪, curr=null

curr এখন null — কাজ শেষ। নতুন হেড: ৪ → ৩ → ২ → ১ → null

রিকার্সিভ পদ্ধতি (Recursion দিয়ে)

রিকার্সন (Recursion) দিয়ে এই কাজটা লিখলে কোডটা দেখতে অনেক সুন্দর লাগে, কিন্তু এতে O(n) পরিমাণ স্ট্যাক স্পেস (stack space) নষ্ট হয় — অর্থাৎ প্রতিটা নোডের জন্য মেমোরিতে একটা করে স্ট্যাক ফ্রেম তৈরি হয়:

pseudocode
1
2
3
4
5
6
7
function reverse(node):
    if node == null or node.next == null:
        return node  # বেস কেস: এটাই নতুন হেড
    newHead = reverse(node.next)
    node.next.next = node  # সামনের নোডটাকে ঘুরিয়ে নিজের দিকে তাক করাই
    node.next = null       # নিজের সামনের পয়েন্টারটা null করে দিই
    return newHead

রিকার্সন একদম শেষের নোড পর্যন্ত যায়, তারপর আবার উল্টোদিক থেকে ফেরত আসা শুরু করে। ফেরত আসার পথে, প্রতিটা কল তার বাচ্চাকে (child) ঘুরিয়ে নিজের দিকে পয়েন্ট করায়, আর নিজের সামনের পয়েন্টারটা null করে দেয়। একদম শেষের নোডটা (যেটা বেস কেস ছিল) নতুন হেড হিসেবে আনচেঞ্জড অবস্থায় সব রিকার্সিভ কল পার হয়ে একদম ওপরে রিটার্ন হয়ে আসে।

লুপ নাকি রিকার্সন — কোনটা ব্যবহার করবেন?

  • ইটারেটিভ বা লুপ: মেমোরি লাগে মাত্র O(1) — প্রডাকশন কোডে আর অনেক লম্বা লিস্টের জন্য এটাই বেস্ট চয়েস (এতে স্ট্যাক ওভারফ্লোর রিস্ক থাকে না)।
  • রিকার্সিভ: মেমোরি লাগে O(n) — কোড পড়তে এবং বুঝতে সুবিধা হয়, কিন্তু লাখ লাখ নোডের লম্বা লিস্টের জন্য এটা বিশাল রিস্কি।

দুটো পদ্ধতিই O(n) সময়ে বা স্পিডে কাজ করে। ইন্টারভিউতে দুটো পদ্ধতিই লিখে তাদের সুবিধা-অসুবিধা বুঝিয়ে বলাটাই হলো একটা পারফেক্ট উত্তর।

অন্যান্য ভেরিয়েশন

পয়েন্টার নিয়ে এই একই কারসাজি ব্যবহার করে আরও অনেক জটিল কাজ করা যায়:

  • সাবলিস্ট রিভার্স করা — পুরোটা উল্টে না দিয়ে শুধু m পজিশন থেকে n পজিশন পর্যন্ত উল্টে দেওয়া।
  • k-গ্রুপে রিভার্স করা — প্রতি k টা এলিমেন্টের এক একটা গ্রুপ বা চাংক (chunk) ধরে ধরে উল্টে দেওয়া।
  • প্যালিনড্রোম চেক করা — লিস্টের অর্ধেক অংশকে রিভার্স করে প্রথম অর্ধেকের সাথে মিলিয়ে দেখা।

Complexity

ইটারেটিভ রিভার্সাল — সময় (Time)
লিস্টের শুরু থেকে শেষ পর্যন্ত একবার হেঁটে যেতে হয়
লিনিয়ার O(n)
ইটারেটিভ রিভার্সাল — মেমোরি (Space)
শুধু তিনটা পয়েন্টার ভেরিয়েবল লাগে
কনস্ট্যান্ট O(1)
রিকার্সিভ রিভার্সাল — সময় (Time)
প্রতিটা নোডের জন্য একবার করে রিকার্সিভ ফাংশন কল করতে হয়
লিনিয়ার O(n)
রিকার্সিভ রিভার্সাল — মেমোরি (Space)
লিস্টের দৈর্ঘ্যের সমান কল-স্ট্যাক (call stack) মেমোরিতে জমে যায়
লিনিয়ার O(n)
Challenge

ছোট কুইজ

ইটারেটিভ (লুপ) পদ্ধতিতে পয়েন্টার উল্টে দেওয়ার আগে `next = curr.next` লিখে সামনের ঠিকানাটা কেন সেভ করে রাখতে হয়?

পড়া চালিয়ে যান