ਦਿੱਤੀ ਲਿੰਕਡ ਸੂਚੀ ਦੇ ਅੰਤ ਤੋਂ Nth ਨੋਡ ਮਿਟਾਓ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਅਡੋਬ ਐਮਾਜ਼ਾਨ ਆਰਸੀਸੀਅਮ ਤੱਥ Intuit ਜੋਹੋ
ਲਿੰਕਡ-ਲਿਸਟ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ "ਦਿੱਤੀ ਲਿੰਕਡ ਲਿਸਟ ਦੇ ਅੰਤ ਤੋਂ Nth ਨੋਡ ਮਿਟਾਓ" ਦੱਸਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਕੁਝ ਨੋਡਾਂ ਨਾਲ ਲਿੰਕਡ ਸੂਚੀ ਦਿੱਤੀ ਗਈ ਹੈ. ਅਤੇ ਹੁਣ ਤੁਹਾਨੂੰ ਲਿੰਕਡ ਸੂਚੀ ਦੇ ਅੰਤ ਤੋਂ nth ਨੋਡ ਨੂੰ ਹਟਾਉਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਉਦਾਹਰਨ

ਦਿੱਤੀ ਲਿੰਕਡ ਸੂਚੀ ਦੇ ਅੰਤ ਤੋਂ Nth ਨੋਡ ਮਿਟਾਓ

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

ਵਿਆਖਿਆ: ਅੰਤ ਤੋਂ ਦੂਜਾ ਨੋਡ 2 ਹੈ. ਇਸ ਲਈ ਅਸੀਂ ਇਸਨੂੰ ਮਿਟਾ ਦੇਵਾਂਗੇ. ਅਤੇ ਨੋਡ ਨੂੰ ਡਿਲੀਟ ਕਰਨ ਤੋਂ ਬਾਅਦ ਅਸੀਂ ਆਉਟਪੁਟ ਵਿੱਚ ਦਿਖਾਈ ਗਈ ਲਿੰਕਡ ਸੂਚੀ ਦੇ ਨਾਲ ਰਹਿ ਗਏ ਹਾਂ.

ਪਹੁੰਚ

ਲਿੰਕਡ ਲਿਸਟ ਇਕ ਲਕੀਰ ਡਾਟਾ structureਾਂਚਾ ਹੈ ਜੋ ਪੁਆਇੰਟਰਾਂ ਦਾ ਲਾਭ ਲੈਂਦਾ ਹੈ. ਅਤੇ ਇਹ ਸਾਡੇ ਲਈ ਵਾਧੂ ਤੱਤ ਜੋੜਨ ਦੀ ਇੱਕ ਵੱਡੀ ਸ਼ਮੂਲੀਅਤ ਦੀ ਕੋਸ਼ਿਸ਼ ਨੂੰ ਬਚਾਉਂਦਾ ਹੈ. ਹੁਣ ਸਮੱਸਿਆ ਹੈ ਲਿੰਕਡ ਲਿਸਟ ਵਿਚੋਂ nth ਨੋਡ ਨੂੰ ਹਟਾਉਣ ਦੀ. ਇੱਥੇ ਮੈਨੂੰ ਤੁਹਾਨੂੰ ਦੱਸਣਾ ਚਾਹੀਦਾ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਲਿੰਕਡ ਸੂਚੀ ਵਿੱਚ ਨੋਡਾਂ ਦੀ ਸੰਖਿਆ ਪ੍ਰਦਾਨ ਨਹੀਂ ਕੀਤੀ ਜਾਂਦੀ. ਤਾਂ ਫਿਰ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਕਿਹੜਾ ਤਰੀਕਾ ਅਪਣਾਉਣਾ ਚਾਹੀਦਾ ਹੈ? ਜਦੋਂ ਸਾਨੂੰ ਲਿੰਕਡ ਲਿਸਟ ਦੇ ਅੰਤ ਤੋਂ ਨੌਵਾਂ ਨੋਡ ਨੂੰ ਮਿਟਾਉਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਭੋਰਾ ਪਹੁੰਚ

ਇੱਕ ਭੋਲੀ ਪਹੁੰਚ ਪਹਿਲਾਂ ਲਿੰਕ ਕੀਤੀ ਸੂਚੀ ਦੀ ਲੰਬਾਈ ਦੀ ਗਣਨਾ ਜਾਂ ਗਣਨਾ ਕਰਨ ਲਈ ਹੋਵੇਗੀ. ਇਸ ੰਗ ਨਾਲ ਸਾਨੂੰ ਪਹਿਲਾਂ ਲਿੰਕਡ ਸੂਚੀ ਦੇ ਅੰਤ ਤਕ ਲੂਪ ਚਲਾਉਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਪਰ ਲਿੰਕਡ ਸੂਚੀ ਦੀ ਗਣਨਾ ਅੰਤ ਤੋਂ nth ਨੋਡ ਨੂੰ ਹਟਾਉਣ ਵਿੱਚ ਕਿਵੇਂ ਸਹਾਇਤਾ ਕਰੇਗੀ? ਸਮੱਸਿਆ ਦੇ ਹੱਲ ਲਈ ਅਸੀਂ ਪਹਿਲਾਂ ਜੁੜੀ ਸੂਚੀ ਦੀ ਲੰਬਾਈ ਦੀ ਗਣਨਾ ਕਰਾਂਗੇ. ਫਿਰ ਅਸੀਂ ਦਿੱਤੇ ਗਏ ਇੰਪੁੱਟ ਨੂੰ ਲੰਬਾਈ ਤੋਂ ਘਟਾਵਾਂਗੇ. ਹੁਣ ਅਸੀਂ ਸਧਾਰਣ ਕਰਾਂਗੇ ਨੋਡ ਮਿਟਾਓ ਸਿਰ ਤੋਂ ਲੰਬਾਈ n ਦੂਰੀ 'ਤੇ.

ਅਨੁਕੂਲ ਪਹੁੰਚ

ਇਕ ਅਨੁਕੂਲਿਤ ਪਹੁੰਚ ਲਿੰਕਡ ਸੂਚੀ ਦੇ ਆਕਾਰ ਦੀ ਗਣਨਾ ਕੀਤੇ ਬਿਨਾਂ ਹੋਵੇਗੀ. ਇਸ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਇੱਕ ਚਾਲ ਹੈ. ਪਹਿਲਾਂ, ਅਸੀਂ ਇਕ ਨੋਡ ਨੂੰ ਲੰਘਦੇ ਹਾਂ ਜੋ ਸ਼ੁਰੂਆਤ ਤੋਂ ਬਾਅਦ ਨੌਵੇਂ ਨੋਡ ਤਕ ਸਿਰ ਵਜੋਂ ਅਰੰਭ ਕੀਤਾ ਜਾਂਦਾ ਹੈ. ਹੁਣ ਅਸੀਂ ਇੱਕ ਨੋਡ ਤੇ ਖੜੇ ਹਾਂ ਜੋ ਸ਼ੁਰੂਆਤੀ ਨੋਡ (ਸਿਰ) ਤੋਂ n ਦੇ ਬਰਾਬਰ ਦੂਰੀ ਤੇ ਹੈ. ਫਿਰ ਅਸੀ ਸਿਰ ਦੇ ਬਰਾਬਰ ਇੱਕ ਨਵਾਂ ਵੇਰੀਏਬਲ ਅਰੰਭ ਕਰਦੇ ਹਾਂ. ਫਿਰ ਦੋਵੇਂ ਨੋਡਾਂ ਨੂੰ ਟ੍ਰਾਂਸ ਕਰਨਾ ਸ਼ੁਰੂ ਕਰੋ ਜਦੋਂ ਤੱਕ ਕਿ ਪਹਿਲਾ ਨੋਡ ਲਿੰਕਡ ਸੂਚੀ ਦੇ ਆਖਰੀ ਨੋਡ ਤੱਕ ਨਹੀਂ ਪਹੁੰਚਦਾ. ਉਸ ਸਮੇਂ ਸਾਡਾ ਦੂਜਾ ਪਰਿਵਰਤਨ ਅੰਤ ਤੋਂ n + 1th ਨੋਡ ਤੇ ਹੋਵੇਗਾ. ਹੁਣ ਤੁਹਾਨੂੰ ਅਗਲਾ ਨੋਡ ਹਟਾਉਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਕੋਡ

ਦਿੱਤੀ ਲਿੰਕਡ ਸੂਚੀ ਦੇ ਅੰਤ ਤੋਂ Nth ਨੋਡ ਨੂੰ ਮਿਟਾਉਣ ਲਈ 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 ਨੋਡ ਨੂੰ ਮਿਟਾਉਣਾ ਹੈ

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), ਕਿਉਂਕਿ ਅਸੀਂ ਹੁਣੇ ਕੁਝ ਸਥਿਰ ਵੇਰੀਏਬਲ ਸਟੋਰ ਕੀਤੇ ਹਨ ਸਪੇਸ ਦੀ ਗੁੰਝਲਤਾ ਨਿਰੰਤਰ ਹੈ.