ලබා දී ඇති සම්බන්ධිත ලැයිස්තුවේ අවසානයේ සිට Nth node එක මකන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් ආකේසියම් ෆැක්ට්සෙට් ඉන්ටයිට් Zoho
සම්බන්ධිත ලැයිස්තුව

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

“දී ඇති සම්බන්ධිත ලැයිස්තුවේ අවසානයේ සිට Nth node එක මකන්න” යන ගැටලුවේ සඳහන් වන්නේ ඔබට සමහර නෝඩ් සමඟ සම්බන්ධිත ලැයිස්තුවක් ලබා දී ඇති බවයි. දැන් ඔබ සම්බන්ධිත ලැයිස්තුවේ අවසානයේ සිට n වන නෝඩය ඉවත් කළ යුතුය.

උදාහරණයක්

ලබා දී ඇති සම්බන්ධිත ලැයිස්තුවේ අවසානයේ සිට Nth node එක මකන්න

2->3->4->5->6->7
delete 3rd node from last
2->3->4->6->7

පැහැදිලි කිරීම: අවසානයේ සිට 2 වන නෝඩය 6 වේ. එබැවින් අපි එය මකා දමමු. තවද නෝඩය මකා දැමීමෙන් පසු ප්‍රතිදානයේ පෙන්වා ඇති සම්බන්ධිත ලැයිස්තුව අපට ඉතිරිව ඇත.

ප්රවේශය

සම්බන්ධිත ලැයිස්තුව යනු රේඛීය දත්ත ව්‍යුහයකි. තවද මෙය අතිරේක මූලද්‍රව්‍ය එකතු කිරීම සඳහා විශාල ගණනය කිරීමේ උත්සාහයක් ඉතිරි කරයි. දැන් ගැටළුව වන්නේ සම්බන්ධිත ලැයිස්තුවෙන් nth node ඉවත් කිරීමයි. මෙහිදී මම ඔබට පැවසිය යුත්තේ සම්බන්ධිත ලැයිස්තුවේ ඇති නෝඩ් ගණන ඔබට ලබා දී නොමැති බවයි. ගැටලුව විසඳීම සඳහා යමෙකු තෝරා ගත යුතු ප්‍රවේශය කුමක්ද? සම්බන්ධිත ලැයිස්තුවේ අවසානයේ සිට අපට nth node එක මකා දැමීමට අවශ්‍ය වූ විට.

බොළඳ ප්‍රවේශය

බොළඳ ප්‍රවේශයක් වනුයේ පළමුව සම්බන්ධිත ලැයිස්තුවේ දිග ගණනය කිරීම හෝ ගණනය කිරීමයි. සම්බන්ධිත ලැයිස්තුවේ අවසානය දක්වා ප්‍රථමයෙන් ලූපයක් ධාවනය කිරීමට මේ ආකාරයෙන් අපට අවශ්‍ය වේ. නමුත් සම්බන්ධිත ලැයිස්තුව ගණනය කිරීම අවසානයේ සිට n වන නෝඩ් ඉවත් කිරීමට උපකාරී වන්නේ කෙසේද? ගැටළුව විසඳීම සඳහා අපි පළමුව සම්බන්ධිත ලැයිස්තුවේ දිග ගණනය කරමු. එවිට අපි දී ඇති ආදානය දිගින් අඩු කරමු. දැන් අපි සරලවම කරන්නෙමු නෝඩය මකන්න හිස සිට දුර- n දුරින්.

ප්‍රශස්ත ප්‍රවේශය

සම්බන්ධිත ලැයිස්තුවේ ප්‍රමාණය ගණනය නොකර ප්‍රශස්ත ප්‍රවේශයක් වනු ඇත. මෙම ගැටළුව විසඳීම සඳහා උපක්රමයක් තිබේ. පළමුවෙන්ම, ආරම්භයේ සිට n වන නෝඩය තෙක් හිස ලෙස ආරම්භ කර ඇති නෝඩයක් අපි ගමන් කරමු. දැන් අපි ආරම්භක නෝඩයේ (හිස) සිට n ට සමාන දුරින් පිහිටි නෝඩයක සිටිමු. ඉන්පසු අපි හිසට සමාන නව විචල්‍යයක් ආරම්භ කරමු. පළමු නෝඩය සම්බන්ධිත ලැයිස්තුවේ අවසාන නෝඩය කරා ළඟා වන තෙක් නෝඩ් දෙකම හරහා ගමන් කිරීම ආරම්භ කරන්න. එම අවස්ථාවේදී අපගේ දෙවන විචල්‍යය අවසානයේ සිට n + 1 වන නෝඩයේ වේ. දැන් ඔබට අවශ්‍ය වන්නේ ඊළඟ නෝඩය ඉවත් කිරීමයි.

කේතය

ලබා දී ඇති සම්බන්ධිත ලැයිස්තුවේ අවසානයේ සිට Nth node එක මකා දැමීමට C ++ කේතය

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

struct node{
  int data;
  node* next;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

node* deleteNthNodeFromLast(node* head, int n){
    // first move ahead n nodes
    // then start traversing from the start until the end node
    // delete the temporary node
    node* cur = head;
    while(n--){
        cur = cur->next;
        if(!cur){
            cur = head;
            head = head->next;
            free(cur);
            return head;
        }
    }
    node* tmp = head;
    while(cur->next){
        tmp = tmp->next;
        cur = cur->next;
    }
    cur = tmp->next;
    tmp->next = tmp->next->next;
    return head;
}

int main(){
  // create a linked list
  node* head = new node();
  head = create(2);
  head->next = create(3);
  node* toBeDeleted = create(4);
  head->next->next = toBeDeleted;
  head->next->next->next = create(5);
  head->next->next->next->next = create(6);
  head->next->next->next->next->next = create(7);

  cout<<"Old Linked List: ";
  node* tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
  head = deleteNthNodeFromLast(head, 3);

  cout<<endl<<"New Linked List: ";
  tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
}
Old Linked List: 2 3 4 5 6 7
New Linked List: 2 3 4 6 7

ලබා දී ඇති සම්බන්ධිත ලැයිස්තුවේ අවසානයේ සිට Nth node එක මකා දැමීමට ජාවා කේතය

import java.util.*;
class node{
    int data;
    node next;
}

class Main{
    static node create(int data){
        node tmp = new node();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

    static node deleteNthNodeFromLast(node head, int n){
        // first move ahead n nodes
        // then start traversing from the start until the end node
        // delete the temporary node
        node cur = head;
        while(n-- > 0){
            cur = cur.next;
            if(cur == null){
                cur = head;
                head = head.next;
                return head;
            }
        }
        node tmp = head;
        while(cur.next != null){
            tmp = tmp.next;
            cur = cur.next;
        }
        cur = tmp.next;
        tmp.next = tmp.next.next;
        return head;
    }

    public static void main(String[] args){
        // create a linked list
        node head = new node();
        head = create(2);
        head.next = create(3);
        head.next.next = create(4);
        head.next.next.next = create(5);
        head.next.next.next.next = create(6);
        head.next.next.next.next.next = create(7);

        System.out.print("Old Linked List: ");
        node tmp = head;
        while(tmp != null){
            System.out.print(tmp.data+" ");
            tmp = tmp.next;
        }
        head = deleteNthNodeFromLast(head, 3);

        System.out.print("\n"+"New Linked List: ");
        tmp = head;
        while(tmp!=null){
            System.out.print(tmp.data+" ");
            tmp = tmp.next;
        }
    }
}
Old Linked List: 2 3 4 5 6 7 
New Linked List: 2 3 4 6 7

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), මක්නිසාද යත්, අප විසින් සම්බන්ධිත ලැයිස්තුවේ මුළු ප්‍රදේශය හරහා ගමන් කර ඇති අතර එමඟින් අපට රේඛීය කාල සංකීර්ණත්වය වැය වේ.

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

ඕ (1), මන්දයත් අප විසින් නියත විචල්‍යයන් කිහිපයක් ගබඩා කර ඇති නිසා අවශ්‍ය අවකාශයේ සංකීර්ණතාව නියත වේ.