چیک کریں کہ آیا اسٹرنگز کی ایک لنکڈ لسٹ پالینڈوم تشکیل دیتی ہے


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ایپل بلومبرگ کیپٹل ایک سسکو فیس بک گوگل قبر IXL۔ مائیکروسافٹ نیوٹنکس اوریکل پی ٹی ایم ایم Snapchat Uber Yandex
لنکڈ لسٹ لنکڈ لسٹ سلک

مسئلہ یہ بیان

"چیک کریں کہ آیا اسٹرنگز کی لنکڈ لسٹ ایک Palindrome بنتی ہے" میں ہم نے ایک مسئلہ دیا ہے منسلک فہرست ہینڈلنگ سٹرنگ ڈیٹا۔ ایک پروگرام لکھیں تاکہ معلوم ہو کہ اعداد و شمار ایک palindrom تشکیل دیتا ہے یا نہیں۔

مثال کے طور پر

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

وضاحت: مندرجہ بالا مثال میں ہم دیکھ سکتے ہیں کہ تار "بیکڈکب" ایک پالینڈوم ہے

نقطہ نظر

ایک منسلک فہرست دی گئی ہے جس میں ہر نوڈ میں ایک تار ہوتا ہے۔ ہمیں یہ چیک کرنا ہوگا کہ منسلک فہرست میں موجود ڈیٹا ایک پالینڈوم تشکیل دیتا ہے یا نہیں۔ ایک تار a palindrome اگر یہ وہی فارورڈس پڑھتا ہے جس طرح یہ پسماندہ ہوتا ہے۔ مثال کے طور پر ، نمبر "بیکڈکاب" ایک پالینڈوم ہے۔ اگر منسلک فہرست پیلینڈومز تشکیل دیتی ہے اگر آگے اور پیچھے پیچھے ہوتے وقت ان میں عناصر کا ایک ہی ترتیب ہوتا ہے۔

الگورتھم

  1. خالی تار شروع کرو۔
  2. منسلک فہرست کو عبور کریں اور اس تار میں منسلک فہرست میں موجود تمام عناصر کو ذخیرہ کریں۔
  3. مربوط فہرست کو عبور کریں کہ آیا اس سے متعلقہ پہلے اور آخری حرف برابر ہیں یا نہیں۔ اگر کسی موقع پر وہ برابر نہیں ہیں تو پھر یہ ایک پالینڈوم نہیں بنائے گا۔

عمل

سی ++ پروگرام اس بات کی جانچ کرنے کے لئے کہ آیا اسٹرنگس کی لنکڈ لسٹ ایک Palindrome تشکیل دے رہی ہے

#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();
}

جاوا پروگرام چیک کرنے کے لئے کہ آیا اسٹرنگس کی لنکڈ لسٹ ایک Palindrome بنتی ہے

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 دی گئی منسلک فہرست میں موجود نوڈس کی تعداد ہے۔ ہم یہاں سارے اقدار کو ایک تار میں شامل کرتے ہیں اور اس سٹرنگ کو پالینڈوم حالت کے ل check چیک کرتے ہیں۔

خلائی پیچیدگی

اے (ن) کیونکہ ہم دیئے گئے اہتمام کی فہرست کے نوڈ کی تمام اقدار کو ایک کرتے ہوئے تشکیل شدہ تار استعمال کرتے ہیں۔