Nth Node සොයා ගන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇසොලයිට් ඇෙබෝ ඇමේසන් එපික් පද්ධති ෆැක්ට්සෙට් ඉහළ දැමීම MAQ මොනෝටයිප් විසඳුම් Qualcomm Snapdeal
සිටිකෝර්ප් සම්බන්ධිත ලැයිස්තුව සම්බන්ධිත ලැයිස්තුව

ගැටළු ප්රකාශය

“Find Nth Node” ගැටලුවේදී අපි ලබා දී ඇත්තේ a සම්බන්ධිත ලැයිස්තුව nth node එක හොයාගන්න. වැඩසටහන දත්ත අගය n වන නෝඩයේ මුද්‍රණය කළ යුතුය. N යනු ආදාන පූර්ණ සංඛ්‍යා දර්ශකයයි.

උදාහරණයක්

3
1 2 3 4 5 6
3

ප්රවේශය

සම්බන්ධිත ලැයිස්තුවක් ලබා දී ඇති අතර අපට n-th node එක සොයාගත යුතුය. අපට හෙඩ් නෝඩයට දර්ශකය ඇත.  හෙඩ් නෝඩයට යොමු වන කර්ර් පොයින්ටරයක් ​​අපට නිර්මාණය කළ හැකි අතර, සම්බන්ධිත ලැයිස්තුව හරහා නැවත ගමන් කරන අතරතුර අප සිටින නෝඩ් ගණන ගණනය කිරීමට විචල්‍යයක් ද ගනිමු. ගණන් විචල්‍යය 1 ට ආරම්භ කරන්න. එක් එක් පුනරාවර්තනයේදී, ගණන් කිරීමේ අගය n ට සමාන දැයි අපි පරීක්ෂා කරමු, එය n ට සමාන නම්, අපි curr-> val නැවත ලබා දෙමු. එසේ නොමැතිනම්, අපි ඊළඟ නෝඩයට ගොස් ගණන් කිරීමේ අගය 1 දක්වා වැඩි කරමු.

ඇල්ගොරිතම

  1. කර්ඩ් පොයින්ටර් ලකුණු හෙඩ් නෝඩ් වෙත ගෙන යන්න, සහ අගය 1 වන ගණන් විචල්‍යය
  2. සම්බන්ධිත ලැයිස්තුව හරහා අනුකරණය කරන්න.
  3. ගණන් කිරීමේ අගය n ට සමාන නම්, curr-> val ආපසු එවන්න
  4. වෙනත් ආකාරයකින් කර්ර් නෝඩය එහි ඊළඟ නෝඩයට යොමු කරන අතර ගණන් කිරීමේ අගය 1 දක්වා වැඩි කරයි.

ක්රියාත්මක කිරීම

සී ++ වැඩසටහන Nth Node සොයා ගැනීම

#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 Node සොයා ගැනීමට ජාවා වැඩසටහන

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) එහිදී n දී ඇති පූර්ණ සංඛ්‍යා අගය වේ. මෙන්න අපි රේඛීය කාලය ගත කරන මූලද්‍රව්‍ය ගණන n වෙත පිවිසෙමු.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1) අපි මෙහි කිසිදු සහායක ඉඩක් භාවිතා නොකරන නිසා.