Nth Düyünü tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Çiy kərpic Amazon Epik Sistemlər Məlumat dəsti Piyada çox yol qət eləmək MAQ Monotip həllər Qualcomm Snapdeal
Citicorp Bağlı siyahı Əlaqəli siyahıBaxılıb 190

Problem bəyanat

"Nth Düyünü Tap" problemində a əlaqəli siyahı ninci nodu tapmaq. Proqram, məlumat dəyərini n-cü qovşaqda yazdırmalıdır. N giriş tam ədədi indeksidir.

misal

3
1 2 3 4 5 6
3

Yanaşma

Bağlı bir siyahı verildiyi üçün n-ci qovluğu tapmalıyıq. Baş düyünə işarə var.  Baş düyünü göstərən bir cərəyan göstəricisi yarada bilərik və eyni zamanda əlaqəli siyahıdan təkrarlayarkən qovşaqlarımızın sayını saymaq üçün bir dəyişən götürürük. Sayı dəyişənini 1-ə başlayın. Hər təkrarda, sayma dəyərinin n-ə bərabər olub olmadığını yoxlayırıq, n-ə bərabərdirsə, curr-> val-ı qaytarırıq. Əks təqdirdə, növbəti qovşağa keçirik və sayma dəyərini 1-ə çatdırırıq.

Alqoritm

  1. Bir cərəyan göstəricisini baş düyünə və dəyəri 1 olan bir sayma dəyişəninə aparın
  2. Bağlı siyahını təkrarlayın.
  3. Sayma dəyəri n-ə bərabərdirsə, cərəyanı> valı qaytarın
  4. Başqa bir cərəyan qovşağını növbəti qovşağına yönəldir və saymanın dəyərini 1-ə çatdırır.

Həyata keçirilməsi

Nth Düyünü Tapmaq üçün C ++ Proqramı

#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 Düyünü Tapmaq üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara n verilmiş tam dəyərdir. Burada xətti vaxt alan n sayda elementi ziyarət edirik.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

Translate »