মডিউল ৯: STL List and Cycle Detection

মডিউল ৯_০: Introduction

STL List Built In Functions list:

Constructor

Name	Details	Time Complexity
list<type> myList;	Construct a list with 0 elements.	O(1)
list<type> myList(N);	Construct a list with N elements and the value will be garbage.	O(N)
list<type> myList(N,V);	Construct a list with N elements and the value will be V.	O(N)
list<type> myList(list2);	Construct a list by copying another list list2.	O(N)
list<type> myList(A,A+N);	Construct a list by copying all elements from an array A of size N.	O(N)

Capacity

Name	Details	Time Complexity
myList.size()	Returns the size of the list.	O(1)
myList.max_size()	Returns the maximum size that the vector can hold.	O(1)
myList.clear()	Clears the list elements. Do not delete the memory, only clear the list.	O(N)
myList.empty()	Return true/false if the list is empty or not.	O(1)
myList.resize()	Change the size of the list.	O(K); where K is the difference between new size and current size.

Modifiers

Name	Details	Time Complexity
myList = or myList.assign(list2.begin(),list2.end())	Assign another list.	O(N)
myList.push_back()	Add an element to the tail.	O(1)
myList.push_front()	Add an element to the head.	O(1)
myList.pop_back()	Delete the tail.	O(1)
myList.pop_front()	Delete the head.	O(1)
myList.insert()	Insert elements at a specific position.	O(N+K); where K is the number of elements to be inserted.
myList.erase()	Delete elements from a specific position.	O(N+K); where K is the number of elements to be deleted.
replace(myList.begin(),myList.end(),value,replace_value)	Replace all the value with replace_value. Not under a list STL.	O(N)
find(myList.begin(),myList.end(),V)	Find the value V. Not under a list STL.	O(N)

Operations

Name	Details	Time Complexity
myList.remove(V)	Remove the value V from the list.	O(N)
myList.sort()	Sort the list in ascending order.	O(NlogN)
myList.sort(greater<type>())	Sort the list in descending order	O(NlogN)
myList.unique()	Deletes the duplicate values from the list. You must sort the list first.	O(N), with sort O(NlogN)
myList.reverse()	Reverse the list.	O(N)

Element Access

Name	Details	Time Complexity
myList.back()	Access the tail element.	O(1)
myList.front()	Access the head element.	O(1)
next(myList.begin(),i)	Access the ith element	O(N)

Iterators

Name	Details	Time Complexity
myList.begin()	Pointer to the first element.	O(1)
myList.end()	Pointer to the last element.	O(1)

এই মডিউল শেষে আমরা যা যা শিখবোঃ

1. STL List সম্পর্কে জানবো
2. Singly Linked List Reverse করা সম্পর্কে জানবো
3. Doubly Linked List Reverse করা সম্পর্কে জানবো
4. Singly Linked List এর Cycle Detect করা দেখবো

List Constructors

লিস্ট হলো ভেক্টরের মতো একটি Standard Library বা বিল্ট-ইন ডাটা স্ট্রাকচার। এটি Doubly Linked List এর মতো কাজ করে। অর্থাৎ Doubly Linked List এ যা যা করা সম্ভব তার সব কিছু এই List STL এ করা যাবে ।

ভেক্টরে কন্সট্রাক্টর এর সাহায্যে আমরা যে যে কাজ গুলো করতে পারতাম ঠিক এক ই ভাবে List এও ঐসব কাজ করা যাবে।

প্রথমে দেখে নেয়া যাক কীভাবে লিস্ট ইনিশিয়ালাইজ করা যায়।

১ম টাইপঃ

যদি আমরা না জানি initially আমাদের List এর সাইজ কতো হবে সেই ক্ষেত্রে আমরা কোন সাইজ ছাড়া List ডিক্লেয়ার করবো। নিচের মতো প্রথমে list keyword ব্যবহার করে কোন টাইপের ডেটা রাখতে চাচ্ছেন তার ডাটা টাইপ দিতে হবে এবং ঐ list এর নাম দিতে হবে।

Type 1 :
 list< data_type > list_name ;

 Code :
     list< int > my_list ; // এর মাধ্যমে ইন্টিজার ডাটা টাইপের একটি list তৈরি হবে
     list< char > my_list ; // এর মাধ্যমে ক্যারেক্টার ডাটা টাইপের একটি list তৈরি হবে
     list< float > my_list ; // এর মাধ্যমে ফ্লোট ডাটা টাইপের একটি list তৈরি হবে
     list< long long > my_list ; // এর মাধ্যমে লং লং ইন্টিজার ডাটা টাইপের একটি list তৈরি হবে

২য় টাইপঃ

আমরা যদি আগে থেকেই আমাদের কী পরিমাণ ডাটা দেয়া থাকবে তা জানতে পারি , তবে সেক্ষেত্রে আমরা একটি নির্দিষ্ট সাইজের List ডিক্লেয়ার করতে পারবো। এই ক্ষেত্রে List টি মেমরি তে নির্দিষ্ট সাইজের জায়গা দখল করে নিবে। এবং ভ্যালু ইনপুট না দেয়া পর্যন্ত Garbage value রেখে দিবে। নিচের মতো প্রথমে list keyword ব্যবহার করে কোন টাইপের ডেটা রাখতে চাচ্ছেন তার ডাটা টাইপ দিতে হবে এবং ঐ list এর নাম দিতে হবে এবং একই সাথে লিস্টের সাইজ টা দিয়ে দিতে হবে।

Type 2 :
 list< data_type > list_name (size) ;

 Code :
     list< int > my_list (100) ; // এর মাধ্যমে 100 সাইজের ইন্টিজার ডাটা টাইপের একটি list তৈরি হবে
     list< char > my_list (50) ; // এর মাধ্যমে 50 সাইজের ক্যারেক্টার ডাটা টাইপের একটি list তৈরি হবে
     list< float > my_list (30) ; // এর মাধ্যমে 30 সাইজের ফ্লোট ডাটা টাইপের একটি list তৈরি হবে
     list< long long > my_list (40) ; // এর মাধ্যমে 40 সাইজের লং লং ইন্টিজার ডাটা টাইপের একটি list তৈরি হবে

৩য় টাইপঃ

আমরা যদি আগে থেকেই আমাদের কী পরিমাণ ডাটা দেয়া থাকবে তা জানতে পারি, তবে সেক্ষেত্রে আমরা একটি নির্দিষ্ট সাইজের List ডিক্লেয়ার করতে পারবো। List টি মেমরি তে নির্দিষ্ট সাইজের জায়গা দখল করে নিবে। এবং আমরা গারবেজ ভ্যালু এর পরবর্তীতে আমাদের পছন্দের ভ্যালু দিয়ে ঐ জায়গা গুলো পূরণ করতে পারবো । নিচের মতো প্রথমে list keyword ব্যবহার করে কোন টাইপের ডেটা রাখতে চাচ্ছেন তার ডাটা টাইপ দিতে হবে, List এর নাম দিতে হবে, List এর সাইজ দিতে হবে এবং একই সাথে ঐ List এর প্রত্যেকটি ভ্যালু কি দিয়ে ইনিশিয়ালাইজ করতে চাই তাও দিয়ে দিতে হবে।

Type 3 :
 list< data_type > list_name (size,intitial_value) ;

 Code :
     list< int > v (100,10) ; // এর মাধ্যমে 100 সাইজের ইন্টিজার ডাটা টাইপের একটি list তৈরি হবে যার প্রত্যেকটি Node এর ভ্যালু হবে ১০
     list< char > v (50,'a') ; // এর মাধ্যমে 50 সাইজের ক্যারেক্টার ডাটা টাইপের একটি list তৈরি হবে যার প্রত্যেকটি Node এর ভ্যালু হবে 'a'
     list< float > v (30,2.5) ; // এর মাধ্যমে 30 সাইজের ফ্লোট ডাটা টাইপের একটি list তৈরি হবে যার প্রত্যেকটি Node এর ভ্যালু হবে ২.৫
     list< long long > v (40,100) ; // এর মাধ্যমে 40 সাইজের লং লং ইন্টিজার ডাটা টাইপের একটি list তৈরি হবে

৪ তম টাইপঃ

যদি আমরা চাই একটি লিস্ট কে আরেকটি লিস্ট এর মধ্যে কপি করে নিতে তবে আমরা নিচের মতো করে কোড লিখতে পারি । একই সাথে আরেকটি Array এবং ভেক্টর থেকেও এই কাজ করা যাবে

list < int > my_list1 = {1,2,3,4} ; // একটি list ডিক্লেয়ার করে সেখানে এই ভ্যালু গুলা দিয়ে ইনিশিয়ালাইজ করলাম

list < int > my_list (my_list1) ; // আরেকটি list my_list এ my_list1 এর সকল ভ্যালু সমূহ কপি হয়ে যাবে।

// একই ভাবে আমরা array কপি করতে পারবো।

int array[5] = {1,2,3,4,5} ;

list< int > copy_list (array,array+5) ; // array er সব ভ্যালু list কপি হয়ে যাবে

// একই ভাবে আমরা ভেক্টর কপি করতে পারবো।

vector< int > v = {1,2,3,4,5} ;

list< int > copy_list (v.begin(),v.end()) ; // vector er সব ভ্যালু এই list এ কপি হয়ে যাবে

List এর প্রতিটি element কে সহজে এক্সেস করার উপায়ঃ

আমরা Range Based For loop এর সাহায্যে এই কাজ টি সহজে করতে পারি।

list < int > my_list = {1,2,3,4} ;

for ( int element : my_list) { // প্রতেকটি element ইটারেশন হয়ে element এর মধ্যে জমা হবে
cout << element << endl ; // element টি প্রিন্ট করে দিচ্ছি
}

List Modifiers Functions

List কে মডিফাই করার বিভিন্ন ফাংশনঃ

List Assign: আমরা চাইলে একটি List এ আরেকটি List এসাইন করতে পারি।

যদি ঐ দুইটি List সাইজ সমান হয় , সেক্ষেত্রে এই এসাইনের টাইম কমপ্লেক্সিটি হবে O(1) , অন্যথায় এর টাইম কমপ্লেক্সিটি হবে O(N)

list< int > my_list = {1,2,3,4} ;

list< int > new_list ;

new_list = my_list ; // new_list এর মধ্যে my_list er সব ভ্যালু এসাইন হয়ে যাবে।

push_back() -> এই ফাংশনের মাধ্যমে আমরা List এর শেষের দিকে একটি ভ্যালু insert করতে পারি । অর্থাৎ এটি insert_at_tail এর মতো কাজ করে। একটি ভ্যালু insert করার পর list টির সাইজ ১ বেড়ে যাবে। এই ফাংশনের টাইম কমপ্লেক্সিটি হলো O(1).

list< int > my_list = {1,2,3,4} ;
my_list.push_back(6) ; // ডান সাইডে ভ্যালু ৬ insert করবে

for( int element : my_list ) {
    cout << element << " " ;
}
// 1 2 3 4 6

push_front() -> এই ফাংশনের মাধ্যমে আমরা List এর প্রথম দিকে একটি ভ্যালু insert করতে পারি । অর্থাৎ এটি insert_at_head এর মতো কাজ করে। একটি ভ্যালু insert করার পর list টির সাইজ ১ বেড়ে যাবে। এই ফাংশনের টাইম কমপ্লেক্সিটি হলো O(1).

list< int > my_list = {1,2,3,4} ;
my_list.push_front(6) ; // বাম সাইডে ভ্যালু ৬ insert করবে

for( int element : my_list ) {
    cout << element << " " ;
}
// 6 1 2 3 4

pop_back() -> এই ফাংশনের সাহায্যে আমরা List এর সর্ব ডানের ভ্যালুটি ডিলিট করতে পারি। ভ্যালু কমে যাওয়ার কারণে List এর সাইজ ও ১ কমে যাবে। এই ফাংশনের টাইম কমপ্লেক্সিটি O(1).

list< int >my_list = {5,6,7,8,9} ;
my_list.pop_back() ; // ডান সাইডে ভ্যালু 9 delete হয়ে যাবে

for( int element : my_list) {
    cout << element << " " ;
}
// 5 6 7 8

pop_front() -> এই ফাংশনের সাহায্যে আমরা List এর সর্ব বামের ভ্যালুটি ডিলিট করতে পারি। ভ্যালু কমে যাওয়ার কারণে List এর সাইজ ও ১ কমে যাবে। এই ফাংশনের টাইম কমপ্লেক্সিটি O(1).

list< int >my_list = {10,5,6,7,8} ;

my_list.pop_front() ; // বাম সাইডে ভ্যালু ১০ delete হয়ে যাবে

for( int element : my_list) {
    cout << element << " " ;
}
// 5 6 7 8

my_list.insert(): এই ফাংশনের সাহায্যে আমরা List এর যেকোন index (not similar to array) এ ভ্যালু এড করতে পারবো। এই ফাংশনের টাইম কমপ্লেক্সিটি হলো O(N+K) যেখানে N হলো list এর সাইজ এবং K হলো আমরা কয়টি ভ্যালু insert করবো তার সংখ্যা।

ধরেন আমরা চাচ্ছি আমাদের list এর k তম index ভ্যালু ১০ এড করতে। এই ক্ষেত্রে আমরা লিখবো , তার my_list.insert(next(my_list.begin(),k),value) এবং তার ভ্যালু। next() হলো একটি ফাংশন যার সাহায্যে আমরা List এর শুরু থেকে শুরু কোন একটি index এর পয়েন্টার পাবো।

list< int > my_list = {5,6,7,8,9} ;

my_list.insert( next(my_list.begin(),2) , 10 ) // list টির ২ নাম্বার index ১০ insert হয়ে যাবে।

for( auto element : my_list) {
    cout << element << " " ;
}
// 5 6 10 7 8 9

ভেক্টরের মতো replace and find ও List এর ক্ষেত্রে কাজ করে

replace() -> এই ফাংশনের সাহায্যে আমরা list এর কোন একটি নির্দিষ্ট রেঞ্জের একটি নির্দিষ্ট ভ্যালুকে অন্য একটি ভ্যালু দিয়ে রিপ্লেস করে দিতে পারি। এই ফাংশনের টাইম কমপ্লেক্সিটি হলো O(N) .

Syntax : replace(my_list.begin() , my_list.end() , target_value , change_value)

list< int >my_list = {1,2,3,4,7,6,4,5,4,3,4} ;
replace(my_list.begin() , my_list.end() , 4, 100) // এই ফাংশন টি list এর যে যে স্থানে ভ্যালু 4 আছে তা চেঞ্জ করে 100 করে দিবে
for( int element : my_list) {
    cout << element << " " ;
}
// Output : 1 2 3 100 7 6 100 5 100 3 100

find() -> এই ফাংশনের সাহায্যে আমরা List এর কোন একটি ভ্যালু আছে কিনা খুজে দেখতে পারি। এই ফাংশন আমাদের একটি ইটারেটর রিটার্ন করে যা ঐ ভ্যালুটির ইন্ডেক্সে পয়েন্ট করা থাকে, আর যদি ভ্যালুটি খুজে না পায় তবে my_list.end() এ পয়েন্ট করে থাকে । এই ফাংশনের টাইম কমপ্লেক্সিটি হলো O(N).

Syntax : find(my_list.begin() , my_list.end() , target_value )

list< int > my_list = {1,2,3,4,7,6,4,5,4,3,4} ;
auto it = find(my_list.begin() , my_list.end() , 6) ; // ৬ ভ্যালুটি list এর মধ্যে পেলে প্রথম যে জায়গায় ভ্যালুটি আছে তার ইটারেটর টা রিটার্ন করা হবে

if( it !=my_list.end()) { // যদি ভ্যালুটি পাওয়া না যায় তবে it তে my_list.end() স্টোর হবে।
    cout << "found the value " << *it << endl ; // যেহেতু ইটারেটর একটি পয়েন্টার এর মতো কাজ করে , তাই আমরা it কে dereferencing করে তার ভ্যালু দেখতে পারবো
}
else {
    cout << "not found" << endl ;
}

List Operations and access related functions

আসুন List এর কিছু Operations দেখে নেয়া যাক।

mylist.remove() -> এই ফাংশন টির সাহায্যে আমরা একটি List থেকে একটি নির্দিষ্ট ভ্যালু ডিলিট করে দিতে পারি।

list< int >my_list = {1,2,3,4,7,6,4,5,4,3,4} ;
my_list.remove(4); // এই ফাংশন টি list এর যে যে স্থানে ভ্যালু 4 তা ডিলিট করে দিবে
for( int element : my_list) {
    cout << element << " " ;
}
// Output : 1 2 3 7 6 5 3

mylist.sort() -> এই ফাংশনের সাহায্যে আমরা ছোট থেকে বড় আকারে কোনো একটি list কে সাজাতে পারি। আবার mylist.sort(greater<int>()) এই ভাবে পাস করলে লিস্ট টি বড় থেকে ছোট আকারে সাজানো হয়ে যাবে।

list< int >my_list = {9 , 7 , 1 , 8 , 2 , 5 , 3} ;
my_list.sort(); // ছোট থেকে বড় আকারে সাজিয়ে দিবে
for( int element : my_list) {
    cout << element << " " ;
}
// Output : 1 2 3 5 7 8 9

my_list.sort(greater<int>()); // বড় থেকে ছোট আকারে সাজিয়ে দিবে
for( int element : my_list) {
    cout << element << " " ;
}
// Output : 9 8 7 5 3 2 1

mylist.unique(): এই ফাংশনের সাহায্যে আমরা আমাদের list এর প্রত্যেকটি ভ্যালু Uniquely রাখতে পারি। অর্থাৎ ডুপ্লিকেট ভ্যালু গুলা সব ডিলিট করে দিতে পারি। এই ক্ষেত্রে List টি Sorted আকারে থাকতে হবে। sorted আকারে না থাকলে List টি sorted করে নিতে হবে।

list< int >my_list = {1 , 2 , 3 , 5 , 5 , 6 , 7 , 7 , 7 , 8 , 9} ;
my_list.unique(); // সব ডুপ্লিকেট ভ্যালু রিমুভ করে দিবে।
for( int element : my_list) {
    cout << element << " " ;
}
// Output : 1 2 3 5 6 7 8 9

list < int > my_list2 = { 1 , 3 , 5 , 7 , 9 } ;
my_list2.reverse(); // এই ফাংশনের মাধ্যমে আমরা list টি reverse করে নিতে পারি।
for( int element : my_list2) {
    cout << element << " " ;
}
// Output : 9 7 5 3 1

এইবার দেখে নেয়া যাক কীভাবে আমরা List এর ভ্যালু গুলা এক্সেস করতে পারি

list < int > my_list = { 1 , 3 , 5 , 7 , 9 } ;

// front এর মাধ্যমে আমরা লিস্ট এর Head এর ভ্যালু দেখতে পারি
cout << my_list.front() << endl ; // returns 1

// back এর মাধ্যমে আমরা লিস্ট এর tail এর ভ্যালু দেখতে পারি
cout << my_list.back() << endl ; // returns 9

// next এর সাহায্যে আমরা যেকোন Node এর ইটারেটর পেয়ে যায়

int index = 3 ;

auto iterator_of_index = next(my_list.begin(),index) ;// index ৩ এর পয়েন্টার রিটার্ন করবে
cout << *iterator_of_index << endl ; // ৩ নাম্বার ইন্ডেক্সের ভ্যালু 7 রিটার্ন করবে

Reverse a Singly Linked List

এই মডিউলে আমরা জানবো কীভাবে একটি Singly Linked LIst কে Reverse করা যায়।

প্রথমে দেখে নেয়া যাক একটি Reverse Singly Linked লিস্ট দেখতে কেমন হবে ।

প্রথমে চিন্তা করা যাক, আমাদের Reverse করার চিরচেনা উপায় Two Pointers এর সাহায্যে একটি Singly Linked List , Reverse করা যাবে কিনা। Two Pointers approach এর ক্ষেত্রে আমাদের একটি পয়েন্টার i রাখতে হয় প্রথম Node এ এবং j পয়েন্টার রাখতে হয় শেষ Node এ . এরপর এই দুটি element swap করতে হয় । swap করার পরে আমরা ডানের পয়েন্টার টি এক ঘর বামের দিকে / সামনের দিকের Node এ শিফট করি , এবং j পয়েন্টার টি এক ঘর বামের দিকে / পিছনের Node এ শিফট করি। যেহেতু Singly Linked List এ একটি Node হতে next পয়েন্টার এর সাহায্যে পরের Node এ যাওয়া যায় , এবং prev কোনো Node না থাকায় আগের Node এ যাওয়া যায় না , তাই আমরা i কে পরের Node এ shift করতে পারলেও j কে এর আগের Node এ shift করতে পারবো না। তাই , Singly Linked List এর Reversing এর ক্ষেত্রে Two Pointer Approach ব্যবহার করা যাবে না।

এখন উপায় ?

-> আগের মডিউল গুলোর Recursion এর সাহায্যে Singly Linked List Reverse প্রিন্ট এর ভিডিও তে আমরা দেখেছি , Recursion এর সাহায্যে আমরা Singly LInked List এ back থেকে Traverse করতে পারি। যদিও এটি Recursion এর কল গুলার কারণে Recursion call গুলো ব্যাক এ আসতে থাকা। কারণ আমাদের Recursion call এর timing এর উপর ভিত্তি করে Recursion call গুলো আগে , পরে activate হয়ে থাকে। আমরা যদি চাই , আমাদের Recursion call গুলা আগে হয়ে Singly Linked List এর একদম শেষের Node এ চলে যাক , এবং Call শেষ হবার পর Recursion call ব্যাক করার সময় operation করে আসুক , এই ক্ষেত্রে আমরা আগে Recursion কল করে দেয় , এবং পরবর্তীতে আমাদের অপারেশন ( যেমনঃ Reverse Print এর ক্ষেত্রে Printing Operation) তা আমরা করে থাকি।

যেহেতু আমরা আপাতদৃষ্টিতে Singly Linked List এ ব্যাক এ আসার একটি উপায় পেয়ে গেছি , তাই এই মেথড এ আগানোর চেষ্টা করি। কিছু স্টেপ চিন্তা করি।

যেহেতু Head সবসময় কোনো List এর শুরুর Node এ পয়েন্ট করা থাকে , তাই Reverse করার সময় বর্তমান Linked List এর শেষের Node টি হবে Head Node. আমরা রিকারশন কল করতে করতে শেষের Node এ চলে আসবো , এবং সেই Node যদি শেষ Node হয় তবে , head কে এই Node এ পয়েন্ট করে আমরা Return করা শুরু করবো . এটি হবে আমাদের base case.

সবুজ বক্স এর মাধ্যমে আমরা রিকারশন কল এর কোন Node এ আছি তা দেখছি।

এরপর আমরা যদি দেখি বর্তমান Linked List এর B নোড টির নেক্সট পয়েন্টার C এর দিকে পয়েন্ট করা আছে , কিন্তু Reverse লিস্ট এর ক্ষেত্রে C এর next পয়েন্টার টি B এর দিকে পয়েন্ট করা আছে , অর্থাৎ উলটো। এখন আমরা C Node এ থাকা কালে কখনো B Node এর এড্রেস জানতে পারবো না। তাই C নোড এ থাকা কালে আমরা কোনো কাজ করতে পারবো না। কিন্তু যখন ই আমরা রিকারশন কল এর মাধ্যমে B নোড এ ব্যাক করবো , তখন ই একই সাথে B Node এবং C Node দুইটার ই এক্সেস আমাদের কাছে থাকবে। এরপর আমরা B এর নেক্সট Node ( b->next এর next পয়েন্টার অর্থাৎ B->next ->next পয়েন্টার Null থেকে চেঞ্জ করে B এর দিকে করে দিবো. এবং B এর next পয়েন্টার অর্থাৎ b->next কে Null এর দিকে পয়েন্ট করে দিবো।

এরপর B Node এর কাজ শেষ করে A Node এ ফেরত আসবো। A Node এ আসার পর একই ভাবে আমরা A এবং B Node উভয় Node এর এক্সেস পাবো এরপর B Node ( A->next->next) এর নেক্সট পয়েন্টার A Node এর দিকে করে দিবো । এবং A এর next পয়েন্টার Null এর দিকে করে দিবো।

এইভাবে পুরো Singly Linked List টি Reverse হয়ে যায়।

আশা করি , কন্সেপ্ট টি ঠিক মতো বুঝতে পেরেছেন , কনসেপ্ট বুঝে গেলে এখন আসুন , কোডে তা ছটফট Implement করে ফেলি।

Code:

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node(int val)
    {
        this->val = val;
        this->next = NULL;
    }
};

void print(Node *head)
{
    Node *tmp = head;
    while (tmp != NULL)
    {
        cout << tmp->val << " ";
        tmp = tmp->next;
    }
    cout << endl;
}

void reverse(Node *&head, Node *cur) // cur নিয়েছি যাতে করে head চেঞ্জ না হয়ে যায়, এটি মূলত temp এর মতো কাজ করে
{
    if (cur->next == NULL) // base case
    {
        head = cur; // যদি শেষ Node এ চলে আসি , তবে এটিকে head বলে দিচ্ছি
        return; // এবং রিটার্ন করছি
    }
    reverse(head, cur->next); // আগে সব recursion call গুলা করে দিচ্ছি

    // কল শেষে কোনো একটি Node এ ব্যাক আসার পর
    cur->next->next = cur; // currently যে নোড এ আছি তার নেক্সট এর Node এর next পয়েন্টার চেঞ্জ করে নিজের দিকে করে দিচ্ছি
    cur->next = NULL; // এবং নিজের next পয়েন্টার Null এর দিকে করে দিচ্ছি
}

int main()
{
    Node *head = new Node(10);
    Node *a = new Node(20);
    Node *b = new Node(30);
    Node *c = new Node(40);

    head->next = a;
    a->next = b;
    b->next = c;
    reverse(head, head);
    print(head);
    return 0;
}

Output : 40 30 20 10

Reverse a Doubly Linked List

আমরা গত মডিউলে একটি Singly Linked List কে রিভার্স করা দেখেছি। এখন দেখবো কীভাবে একটি Doubly Linked List কে রিভার্স করা যায়।

যেহেতু আমরা Doubly Linked List এর বাম থেকে ডানে , এবং ডান থেকে বামে দুই দিকে Traverse করতে পারি , তাই এই ক্ষেত্রে আমরা Two Pointer Approach এ চিন্তা করতে পারি।

Two pointer Approach এর সাহায্যে কীভাবে একটি Array Reverse করতে হয় তা আমরা আগের মডিউল গুলাতে দেখেছি । Array এর ক্ষেত্রে আমরা দুটি পয়েন্টার i এবং j নিয়েছিলাম , i তে রেখেছিলাম array এর ০ তম index এবং j তে রেখেছিলাম array এর শেষ element বা n-1 তম index. এরপর আমরা ar[i] এবং ar[j] কে swap করতাম . swap করা শেষে i++ অর্থাৎ i কে এক ঘর সামনে নিয়ে যাবো , এবং j-- অর্থাৎ j কে এক ঘর পিছনে নিয়ে যাবো। এই প্রসেস চলতে থাকবে যতক্ষন i এর ভ্যালু j থেকে ছোট হবে.

Doubly Linked List এর ক্ষেত্রেও আমরা ঠিক সেইম ভাবে কাজ টি করবো।

১। প্রথমে দুটি পয়েন্টার নিবো i এবং j পয়েন্টার নিবো. i কে পয়েন্ট করবো লিস্ট এর Head এ , এবং j কে পয়েন্ট করবো লিস্ট এর tail এ

২। এরপর i যে Node এ পয়েন্ট করা আছে ঐ Node এর ভ্যালু এবং j যে Node এ আছে ঐ Node এর ভ্যালু গুলা swap করবো

৩। swap করার পর , আমরা i পয়েন্টার কে এক ঘর ডানে নিয়ে যাবো অর্থাৎ i = i->next হয়ে যাবে এবং j পয়েন্টার কে এক ঘর বামে নিয়ে যাবো। অর্থাৎ j = j->prev এ নিয়ে যাবো

এই প্রসেস চলতে থাকবে যতক্ষন i!=j এবং i->next != j হবে ।

উপরের প্রসেসে Two Pointers approach বুঝতে আশা করি কারো অসুবিধা নেই। সাধারণত এই কন্ডিশনের লজিক টা বুঝতে অসুবিধা হয়। আসুন দেখে ছবির মাধ্যমে দেখে নেয়া যাক , কীভাবে এই কন্ডিশন এপ্লাই হচ্ছে।

প্রথমে দেখে নেয়া যাক , বিজোড় সংখ্যক নোডের জন্য Stop condition টা কেমন হচ্ছে

এখানে দেখা যাচ্ছে i এবং j পয়েন্টার একটি Node এ এসে মিলিত হয়েছে , এরপর আর আমাদের কোনো swap অপারেশন করার প্রয়োজন নেই তার মানে i==j হলে আমরা লুপ টি ব্রেক করে দিবো।

এরপর দেখে নেয়া যাক , যদি জোড় সংখ্যক Node থাকে তবে কী করা যায়

এখানে দেখা যাচ্ছে ৩য় iteration j বামে মুভ করেছে এবং i ডানে মুভ করেছে। যার কারণে আমাদের কাজ টি ঠিক মতো হবে না। অর্থাৎ এর j এবং i intersect করে move করার আগে তাদের থামাতে হবে। অর্থাৎ 2nd iteration এর সময় আমরা লুপ টি থামিয়ে দিবো। অর্থাৎ i এবং j যখন পাশাপাশি থাকবে অর্থাৎ i এর নেক্সট এ j থাকবে। i ->next !=j যতক্ষন হবেনা ততক্ষন আমরা লুপ চালাবো। পাশাপাশি হলে সেখানে থেমে যাবো।

Code:

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node *prev;
    Node(int val)
    {
        this->val = val;
        this->next = NULL;
        this->prev = NULL;
    }
};

void print_normal(Node *head)
{
    Node *tmp = head;
    while (tmp != NULL)
    {
        cout << tmp->val << " ";
        tmp = tmp->next;
    }
    cout << endl;
}

void reverse(Node *head, Node *tail)
{
    Node *i = head; // i পয়েন্টারকে head এ পয়েন্ট করালাম
    Node *j = tail; // j পয়েন্টারকে tail এ পয়েন্ট করালাম
    while (i != j && i->next != j) // যতক্ষন পর্যন্ত condition True হচ্ছে ততক্ষন লুপ চালাবো
    {
        swap(i->val, j->val); // কারেন্ট i এবং j যে Node এ পয়েন্ট করা আছে ঐ Node গুলার ভ্যালু swap করলাম
        i = i->next; // i কে একঘর ডানে মুভ করলাম
        j = j->prev; // j কে একঘর বামে মুভ করলাম
    }
    swap(i->val, j->val); // Node সংখ্যা জোড় হলে যেহেতু i->next = j কন্ডিশনে loop ব্রেক হবে তখন উপরের লুপে মাঝামাঝি দুটি Node এর ভ্যালু swap হবে না। এইক্ষেত্রে আমরা manually কাজটি করে নিলাম।
}

int main()
{
    Node *head = new Node(10);
    Node *a = new Node(20);
    Node *b = new Node (30) ;
    Node *c = new Node(40) ;
    Node *tail = c ;

    // connection
    head->next = a;
    a->prev = head;
    a->next = b;
    b->prev = a;
    b->next = c;
    c->prev = b;
    reverse(head, tail);
    print_normal(head); // 40 30 20 10

    return 0;
}

Detect Cycle in Singly Linked List

এই মডিউলে আমরা একটি Singly Linked List এ কীভাবে Cycle Detect করতে হয় ।

প্রথমে জেনে নেয়া যাক Cycle বলতে কি বুঝানো হয়েছে। ধরুন আপনার এলাকায় তিনটি ঘর আছে যারা নিজেদের মধ্যে রাস্তা দিয়ে একজন আরেকজনের সাথে যুক্ত আছে নিচের ছবির মতো

এখন আমরা যদি A ঘর থেকে সোজা রাস্তা ধরে যাত্রা শুরু করি তবে B ঘরে যাবো , B ঘর থেকে যাবো C ঘরে , এবং C ঘর থেকে যাবো A ঘরে। অর্থাৎ যে ঘর (A) থেকে যাত্রা শুরু করেছিলাম আবার যাত্রা শেষ করে সেই ঘরেই ফিরে এসেছি। এইখানে রাস্তা গুলো এই ঘর গুলোর মধ্যে একটি সাইকেল বা লুপ তৈরি করেছে । এটিকে বলা হয় Cycle.

এখন দেখে নেয়া যাক একটি Singly Linked List এ সাইকেল থাকলে তা দেখতে কেমন হবে ।

এখানে যদি আমরা Y Node হতে next , নেক্সট করে সামনে যেতে থাকি তবে যেহেতু আপাত দৃষ্টিতে Last Node হলো C . এবং C Node এর নেক্সট এ গেলে আমরা আবার Y Node এ ফিরে আসবো। অর্থাৎ এখানে একটি Cycle ক্রিয়েট হয়েছে.

Singly Linked List এ Cycle Detect করার জন্য আমরা একটি নতুন টেকনিক শিখবো । যাকে বলা হয় Hare and Tortoise বা Slow and Fast টেকনিক।

আগে দেখে নেয়া যাক এই টেকনিক কীভাবে Implement করতে হয়।

১। শুরুতে আমরা Two Pointers টেকনিক এর মতো দুটি পয়েন্টার নিবো যার নাম হবে Hare , Tortoise. যা Initially Singly Linked List এর প্রথম Node এ থাকবে।

২। এরপর Hare (fast) পয়েন্টার কে ২ ঘর করে করে সামনে নিতে থাকবো , এবং Tortoise (slow) পয়েন্টার কে একঘর একঘর সামনে নিতে থাকবো।

৩। দুটি পয়েন্টার যদি কোনো একটি মোমেন্ট এ একই জায়গায় মিলিত হয় তবে সেক্ষেত্রে আমরা বলতে পারবো , LInked List এ একটি Cycle রয়েছে। যদি মিলিত না হয় তবে সেই ক্ষেত্রে বলা যাবে , উক্ত Linked List এ কোনো Cycle নাই।

আসেন কোড এর মাধ্যমে Implementation টা দেখি।

Code :

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node(int val)
    {
        this->val = val;
        this->next = NULL;
    }
};

int main()
{
    Node *head = new Node(10);
    Node *a = new Node(20);
    Node *b = new Node(30);

    head->next = a;
    a->next = b;

    Node *slow = head; // slow পয়েন্টার টি head এ পয়েন্ট করেছি
    Node *fast = head; // fast পয়েন্টার টি head এ পয়েন্ট করেছি
    bool flag = false; // Cycle পেয়েছি কিনা চেক করার জন্য flag রাখছি
    while (fast != NULL && fast->next != NULL) // fast এবং fast->next যতক্ষন না হচ্ছে ততক্ষন লুপ চালাচ্ছি
    {
        slow = slow->next; // slow পয়েন্টার কে এক ঘর সামনে নিয়ে যাচ্ছি
        fast = fast->next->next; // fast পয়েন্টার কে দুই ঘর সামনে নিয়ে যাচ্ছি
        if (fast == slow) // যদি কোনো Moment এ fast এবং slow পয়েন্টার same node এ পয়েন্ট করা থাকে
        {
            flag = true; // তবে Cycle Detect হয়েছে এবং flag এর মান True করে দিলাম
            break;
        }
    }
    if (flag == true) // flag এর মান true হলে Cycle পাওয়া গেছে
        cout << "Cycle Detected" << endl;
    else
        cout << "No Cycle" << endl; // else কোনো cycle নেই
    return 0;
}