സ്ട്രിംഗുകളുടെ ലിങ്ക്ഡ് ലിസ്റ്റ് ഒരു പലിൻഡ്രോം ഉണ്ടാക്കുന്നുണ്ടോയെന്ന് പരിശോധിക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് ക്യാപിറ്റൽ വൺ സിസ്കോ ഫേസ്ബുക്ക് ഗൂഗിൾ എടുക്കുക IXL മൈക്രോസോഫ്റ്റ് നൂതാനിക്സ് ഒറാക്കിൾ Paytm Snapchat യൂബർ യാൻഡക്സ്
ലിങ്ക്ഡ്-ലിസ്റ്റ് ലിങ്ക്ഡ് ലിസ്റ്റ് സ്ട്രിംഗ്

പ്രശ്നം പ്രസ്താവന

“സ്ട്രിംഗുകളുടെ ഒരു ലിങ്ക്ഡ് ലിസ്റ്റ് ഒരു പലിൻഡ്രോം ഉണ്ടാക്കുന്നുണ്ടോയെന്ന് പരിശോധിക്കുക” എന്നതിൽ ഞങ്ങൾ നൽകിയിട്ടുണ്ട് ലിങ്കുചെയ്‌ത ലിസ്റ്റ് സ്ട്രിംഗ് ഡാറ്റ കൈകാര്യം ചെയ്യുന്നു. ഡാറ്റ ഒരു പലിൻഡ്രോം ഉണ്ടാക്കുന്നുണ്ടോ എന്ന് പരിശോധിക്കാൻ ഒരു പ്രോഗ്രാം എഴുതുക.

ഉദാഹരണം

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

വിശദീകരണം: മുകളിലുള്ള ഉദാഹരണത്തിൽ “bacdcab” എന്ന സ്ട്രിംഗ് ഒരു പലിൻഡ്രോം ആണെന്ന് നമുക്ക് കാണാൻ കഴിയും

സമീപനം

ഓരോ നോഡിലും ഒരു സ്ട്രിംഗ് അടങ്ങിയിരിക്കുന്ന ഒരു ലിങ്കുചെയ്‌ത ലിസ്റ്റ് നൽകിയിരിക്കുന്നു. ലിങ്കുചെയ്‌ത ലിസ്റ്റിലെ ഡാറ്റ ഒരു പലിൻഡ്രോം ഉണ്ടാക്കുന്നുണ്ടോയെന്ന് പരിശോധിക്കേണ്ടതുണ്ട്. ഒരു സ്ട്രിംഗ് a palindrome അത് പിന്നോക്കം പോകുന്ന അതേ ഫോർ‌വേർ‌ഡുകൾ‌ വായിച്ചാൽ‌. ഉദാഹരണത്തിന്, “bacdcab” എന്ന സംഖ്യ ഒരു പലിൻഡ്രോം ആണ്. മുന്നോട്ടും പിന്നോട്ടും സഞ്ചരിക്കുമ്പോൾ ഘടകങ്ങളുടെ അതേ ക്രമം ഉണ്ടെങ്കിൽ ലിങ്കുചെയ്‌ത ലിസ്റ്റ് പലിൻഡ്രോമുകൾ ഉണ്ടാക്കുന്നു.

അൽഗോരിതം

  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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ n തന്നിരിക്കുന്ന ലിങ്കുചെയ്‌ത ലിസ്റ്റിലുള്ള നോഡുകളുടെ എണ്ണം. ഇവിടെ ഞങ്ങൾ ഒരു സ്ട്രിംഗിൽ എല്ലാ മൂല്യങ്ങളും ചേർത്ത് പലിൻഡ്രോം അവസ്ഥയ്ക്കായി ആ സ്ട്രിംഗിനായി പരിശോധിക്കുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) കാരണം, ഒരു നിശ്ചിത പട്ടികയുടെ നോഡിന്റെ എല്ലാ മൂല്യങ്ങളും സംയോജിപ്പിച്ച് രൂപീകരിച്ച ഒരു സ്ട്രിംഗ് ഞങ്ങൾ ഉപയോഗിക്കുന്നു.