Mündəricat
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
- Bir cərəyan göstəricisini baş düyünə və dəyəri 1 olan bir sayma dəyişəninə aparın
- Bağlı siyahını təkrarlayın.
- Sayma dəyəri n-ə bərabərdirsə, cərəyanı> valı qaytarın
- 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.