স্ট্রিংগুলির একটি লিঙ্কযুক্ত তালিকাটি প্যালিনড্রোম তৈরি করে কিনা তা পরীক্ষা করুন  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ক্যাপিটাল ওয়ান সিসকো ফেসবুক গুগল দখল আইএক্সএল মাইক্রোসফট Nutanix আকাশবাণী Paytm Snapchat উবার ইয়ানডেক্স
যোজিত তালিকা যোজিত তালিকা স্ট্রিং

সমস্যা বিবৃতি  

"স্ট্রিংগুলির একটি লিঙ্কযুক্ত তালিকার একটি প্যালিনড্রোম তৈরি হয় কিনা তা পরীক্ষা করুন" তে আমরা একটি সমস্যার সমাধান করেছি যোজিত তালিকা স্ট্রিং ডেটা হ্যান্ডলিং। ডেটা প্যালিনড্রম গঠন করে কিনা তা পরীক্ষা করতে একটি প্রোগ্রাম লিখুন।

উদাহরণ  

ba->c->d->ca->b
1

ব্যাখ্যা: উপরের উদাহরণে আমরা দেখতে পাচ্ছি যে স্ট্রিং "ব্যাকড্যাব" একটি প্যালিনড্রোম

অভিগমন  

একটি লিঙ্কযুক্ত তালিকা দেওয়া হয়েছে যাতে প্রতিটি নোডে একটি স্ট্রিং থাকে। লিঙ্কযুক্ত তালিকার ডেটা প্যালিনড্রোম গঠন করে কিনা তা আমাদের দেখতে হবে। একটি স্ট্রিং ক প্যালিনড্রোম এটি যদি পিছনের মতো একই ফরোয়ার্ডগুলি পড়ে। উদাহরণস্বরূপ, "ব্যাকড্যাব" নম্বরটি একটি প্যালিনড্রোম। একটি লিঙ্কযুক্ত তালিকা প্যালিনড্রোমগুলি ফর্ম করে যদি তাদের সামনে এবং পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে পিছনে জড়িত যখন উপাদানগুলির একই ক্রম থাকে।

অ্যালগরিদম  

  1. একটি খালি স্ট্রিং শুরু করুন।
  2. লিঙ্কযুক্ত তালিকাটি অতিক্রম করুন এবং সেই স্ট্রিংটিতে লিঙ্কযুক্ত তালিকার সমস্ত উপাদান সঞ্চয় করুন।
  3. লিঙ্কযুক্ত তালিকায় তার প্রথম এবং শেষের অক্ষরগুলি সমান কিনা তা যাচাই করতে যান। যদি কোনও পর্যায়ে তারা সমান না হয় তবে এটি প্যালিনড্রোম গঠন করবে না।

বাস্তবায়ন  

স্ট্রিংগুলির লিঙ্কযুক্ত তালিকাটি প্যালিনড্রোম তৈরি করে কিনা তা পরীক্ষা করতে সি ++ প্রোগ্রাম

#include<bits/stdc++.h>
using namespace std;

class MyLinkedList {
public:
    struct ListNode {
        ListNode *next;
        string val;
        ListNode(string a): next(NULL), val(a){}
    };
    ListNode *head;

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(string val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    bool isPlalindrome(){
    	string str = "";
    	ListNode* ptr = head;
    	while(ptr){
    		str+=ptr->val;
    		ptr = ptr->next;
    	}
    	int n = str.size();
    	for(int i=0;i<n/2;i++){
    		if(str[i]!=str[n-i-1]){
    			return false;
    		}
    	}
    	return true;
    }

    void print_list(){
    	ListNode* node = head;
    while(node){
      cout<<node->val<<" ";
      node = node->next;
    }
        cout<<endl;
  }
};

int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead("b");
  list->addAtHead("ca");
  list->addAtHead("d");
  list->addAtHead("c");
  list->addAtHead("ba");
  
  cout<<list->isPlalindrome();
}

স্ট্রিংগুলির লিঙ্কযুক্ত তালিকার একটি প্যালিনড্রোম রয়েছে কিনা তা পরীক্ষা করার জন্য জাভা প্রোগ্রাম

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
  
  public static void main (String[] args) throws java.lang.Exception{
    
    MyLinkedList obj = new MyLinkedList();
    obj.addAtHead("b");
    obj.addAtHead("ca");
    obj.addAtHead("d");
    obj.addAtHead("c");
    obj.addAtHead("ba");
    
    System.out.println(obj.isPalindrome());
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          String val = "";
          
          public Node(String val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      
      
      public void addAtHead(String val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
    public boolean isPalindrome(){
      String str="";
      Node curr = head;
      while(curr!=null){
        str+=curr.val;
        curr = curr.next;
      }
      
      int n = str.length();
      for(int i=0;i<n/2;i++){
        if(str.charAt(i)!=str.charAt(n-i-1)){
          return false;
        }
      }
      return true;
    }

    public void printList(){
      Node curr = head;
      while(curr!=null){
        System.out.print(curr.val+" ");
        curr = curr.next;
      }
      System.out.println("");
    }
      
  }
}
1

জটিলতা বিশ্লেষণ  

সময় জটিলতা

উপর) কোথায় n প্রদত্ত লিঙ্কযুক্ত তালিকায় উপস্থিত নোডের সংখ্যা। এখানে আমরা একটি স্ট্রিংয়ে সমস্ত মান যুক্ত করি এবং প্যালিনড্রোম শর্তের জন্য সেই স্ট্রিংটি পরীক্ষা করি।

আরো দেখুন
সাজানো তালিকার দ্বিতীয় থেকে নকল সরান

স্পেস জটিলতা ity

উপর) কারণ আমরা প্রদত্ত একটি রেখাযুক্ত তালিকার নোডের সমস্ত মানকে সম্মিলিত করে গঠিত একটি স্ট্রিং ব্যবহার করি।

0 শেয়ারগুলি
কিচ্কিচ্
ভাগ
ভাগ
পিন
হোয়াটসঅ্যাপ