Գտեք Nth հանգույցը  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ակոլիտ Adobe Amazon Էպիկական համակարգեր Փաստեր Զբոսանք MAQ Մոնոտիպ լուծումներ Qualcomm Snapdeal
Citicorp Կապված ցուցակ LinkedList- ը

Խնդիրի հայտարարություն  

«Գտիր Nth հանգույց» խնդրում մենք տվել ենք ա կապված ցուցակը գտնել n- րդ հանգույցը: Theրագիրը պետք է տվյալների արժեքը տպագրի n-րդ հանգույցում: N - մուտքային ամբողջ ցուցանիշն է:

Օրինակ  

3
1 2 3 4 5 6
3

Մոտեցում  

Հաշվի առնելով կապված ցուցակը, և մենք պետք է գտնենք n- րդ հանգույցը: Մենք ունենք ցուցիչը դեպի գլխի հանգույցը:  Մենք կարող ենք ստեղծել curr ցուցիչ, որը մատնանշում է գլխի հանգույցը, և մենք նաև վերցնում ենք փոփոխական ՝ հաշվելու համար մեր եղած հանգույցների քանակը, մինչդեռ կապակցված ցուցակի միջոցով կրկնվում ենք: Հաշվիչ փոփոխականը սկզբնավորենք 1-ի: Յուրաքանչյուր կրկնության ժամանակ մենք ստուգում ենք, թե արդյոք հաշվարկի արժեքը հավասար է n- ին, եթե այն հավասար է n- ի, մենք վերադարձնում ենք curr-> val: Հակառակ դեպքում մենք անցնում ենք հաջորդ հանգույցին և հաշվարկի արժեքը հասցնում 1-ի:

Ալգորիթմ
  

  1. Վերցրեք curr ցուցիչի կետերը դեպի գլխի հանգույցը և հաշվարկի փոփոխական, որի արժեքը 1 է
  2. Կրկնել կապակցված ցանկը:
  3. Եթե ​​հաշվարկի արժեքը հավասար է n- ին, վերադարձիր curr-> val- ը
  4. Ուրիշը curr հանգույցը ուղղում է դեպի իր հաջորդ հանգույցը և հաշվարկի արժեքը հասցնում 1-ի:

Իրականացման  

C ++ ծրագիր ՝ Nth հանգույց գտնելու համար

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

Java ծրագիր ՝ 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("");
    }
      
  }
}

Բարդության վերլուծություն  

Timeամանակի բարդություն

O (n) որտեղ n տրված ամբողջ արժեքն է: Այստեղ մենք այցելում ենք գծային ժամանակ պահանջող տարրերի քանակ:

Տես նաեւ,
Հատուկ զեղչով վերջնական գներ խանութի Leetcode լուծույթում

Տիեզերական բարդություն

Ո (1) քանի որ մենք այստեղ ոչ մի օժանդակ տարածք չենք օգտագործում: