Nth নোড খুঁজুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় সমষ্টি রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক এপিক সিস্টেম ফ্যাক্সেট আরোহণ ম্যাক মনোোটাইপ সমাধান কোয়ালকম Snapdeal
Citicorp যোজিত তালিকা যোজিত তালিকা

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

"Nth নোড খুঁজুন" সমস্যাটিতে আমরা একটি দিয়েছি যোজিত তালিকা nth নোড খুঁজে। প্রোগ্রামটি নবম নোডে ডেটা মান মুদ্রণ করা উচিত। এন হ'ল ইনপুট পূর্ণসংখ্যা সূচক।

উদাহরণ

3
1 2 3 4 5 6
3

অভিগমন

একটি লিঙ্কযুক্ত তালিকা দেওয়া হয়েছে এবং আমাদের n-th নোডটি সন্ধান করতে হবে। আমরা মাথা নোড পয়েন্টার আছে।  আমরা একটি কার্সার পয়েন্টার তৈরি করতে পারি যা হেড নোডকে নির্দেশ করে, এবং আমরা লিঙ্কযুক্ত তালিকার মাধ্যমে পুনরাবৃত্তি করার সময় আমরা যে নোডগুলি রেখেছি তার সংখ্যা গণনা করতে একটি পরিবর্তনশীলও গ্রহণ করি। গণনা পরিবর্তনশীল 1 টি শুরু করুন। প্রতিটি পুনরাবৃত্তিতে আমরা পরীক্ষা করব যে গণনা মানটি n এর সমান কিনা, যদি এটি n এর সমান হয়, আমরা কারর-> ভালটি ফিরিয়ে দেব। অন্যথায়, আমরা পরবর্তী নোডে চলে যাই এবং গণনার মান 1 এ বাড়িয়ে দেব।

অ্যালগরিদম

  1. হেড নোডের দিকে কারুর পয়েন্টার পয়েন্ট করুন এবং একটি গণনা ভেরিয়েবল নিন যার মান 1
  2. লিঙ্কযুক্ত তালিকার মাধ্যমে আইট্রেট করুন।
  3. গণনার মান যদি n এর সমান হয় তবে কারার-> ভালটি ফেরত দিন
  4. অন্য কারার নোডটিকে তার পরবর্তী নোডের দিকে নির্দেশ করে এবং গণনার মান 1 এ বাড়িয়ে দেয়।

বাস্তবায়ন

সি ++ প্রোগ্রাম নথ নোড সন্ধান করার জন্য

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

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

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(int val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    int nthNode(int n){
    	ListNode* curr = head;
    	int cnt=1;
    	while(curr){
    		if(cnt==n){
    			return curr->val;
    		}
    		curr = curr->next;
    		cnt++;
    	}
    	return -1;
    }

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

int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead(10);
  list->addAtHead(7);
  list->addAtHead(4);
  list->addAtHead(2);

    cout<<list->nthNode(3);
}

জাভা প্রোগ্রাম Nth নোড সন্ধান করুন

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(10);
    obj.addAtHead(7);
    obj.addAtHead(4);
    System.out.println(obj.nthNode(3));
    
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          int val = 0;
          
          public Node(int val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      
      
      public void addAtHead(int val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
      public int nthNode(int n){
      	Node curr = head;
      	int cnt=1;
      	while(curr!=null){
      		if(cnt==n){
      			return curr.val;
      		}
      		curr = curr.next;
      		cnt=cnt+1;
      	}
      	return -1;
      }

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

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

সময় জটিলতা

উপর) কোথায় n প্রদত্ত পূর্ণসংখ্যা মান। এখানে আমরা লিনিয়ার সময় নেয় এমন অনেক সংখ্যক উপাদান পরিদর্শন করি।

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

ও (1) কারণ আমরা এখানে কোনও সহায়ক স্থান ব্যবহার করি না।