Son Nəticəni Silin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Məlumat dəsti Kahin
Bağlı siyahı Əlaqəli siyahıBaxılıb 386

Problem bəyanat

"Son Baş verənləri Sil" problemində a əlaqəli siyahı. Bağlı siyahıdan verilən bir düymənin son meydana gəlməsini silmək üçün bir proqram yazın. Siyahıda dublikatlar ola bilər.

misal

1  2  3  5  2  10
1  2  3  5  2

Yanaşma

Yinelenen maddələr ehtiva edən əlaqəli bir siyahı nəzərə alınaraq, bir elementin son meydana gəlməsini silmək məcburiyyətindəyik.  

Bu problemin arxasındakı əsas intuisiya ondan ibarətdir ki, cari düyün dəyəri key_item dəyərinə bərabər olduqda əvvəlki düyün göstəricisini və cari düyün göstəricisini saxlaya bilərik (son meydana gəlməsini silməli olduğumuz).

Beləliklə, bütün əlaqəli siyahını təkrarladıqdan sonra silməli olduğumuz əvvəlki qovşaq göstəricisinə və qovşaqdakı mövcud qovşaq göstəricisinə sahibik. Buna görə nə ediriksə, əvvəlki növbəti göstəricini indiki növbəti göstərici ilə əvəz edirik. Və maddənin son meydana gəlməsini sildik.

Əvvəlcə baş göstəricisini saxlayan bir düyün göstəricisi götürürük və əvvəlki düyünü və cari düyün göstəricilərini saxlayan daha iki göstərici üstünlük təşkil edir. Sonra əlaqəli siyahını təkrarlayırıq, nə zaman ki, cərəyan sonrakı dəyəri saxladığımız əsas elementin dəyərinə bərabərdirsə, o zaman qovşaq dəyərinə, nə də sonrakı qovşağına keçirik. Və biz nodu növbəti node göstərir. Bütün əlaqəli siyahını təkrarladıqda, əvvəlki cərgənin yanındakı əvvəlini əvəz edirik. 

Və əvvəlki göstərici dəyəri sıfırsa və baş dəyəri düyməyə bərabərdirsə, onda növbəti göstəricini başdan başa dəyişdiririk. Baş açarın ilk və son meydana gəlməsi olduğundan.

Həyata keçirilməsi

Son Baş verənləri Silmək üçü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;
    }
    
    void DeleteLastOccurenceOfKey(int key){
    	ListNode* node = head;
    	ListNode* prev = NULL,*curr=NULL;
    	while(node){
    		if(node->next && node->next->val==key){
    			prev = node;
    			curr = node->next;
    		}
    		node = node->next;
    	}
    	if(prev){
    		prev->next = curr->next;
    	}else if(head->val==key){
    		head = head->next;
    	}
    }

    void print_list(){
    	ListNode* node = head;
    while(node){
      cout<<node->val<<" ";
      node = node->next;
    }
        cout<<endl;
  }
};

int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead(5);
  list->addAtHead(4);
  list->addAtHead(3);
  list->addAtHead(2);
  list->addAtHead(1);
  
  list->print_list();
  
  list->DeleteLastOccurenceOfKey(5);
  list->print_list();
  list->DeleteLastOccurenceOfKey(1);
  list->print_list();
}

Son Sonu Silmə üçü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(5);
    obj.addAtHead(4);
    obj.addAtHead(3);
    obj.addAtHead(2);
    obj.addAtHead(1);
    
    obj.printList();
    obj.DeleteLastOccurenceOfKey(5);
    obj.printList();
    obj.DeleteLastOccurenceOfKey(1);
    obj.printList();
    
  }
  
  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 void DeleteLastOccurenceOfKey(int key) {
        Node node=head;
        Node prev=null;
        Node curr=null;
    
        while(node!=null){
            if(node.next!=null && node.next.val==key){
              prev=node;
              curr=node.next;
            }
            node=node.next;
        }
        if(prev!=null){
        	prev.next=curr.next;
        }else if(head.val == key){
        	head = head.next;
        }
    }

    public void printList(){
      Node curr = head;
      while(curr!=null){
        System.out.print(curr.val+" ");
        curr = curr.next;
      }
      System.out.println("");
    }
      
  }
}
1 2 3 4 5 
1 2 3 4 
2 3 4

Son Baş verənlərin Silinməsi üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n) hara n əlaqəli siyahıda mövcud olan qovşaqların sayıdır. Burada xətti vaxt alan istək nodu əldə edilənə qədər əlaqəli siyahıdan keçirik.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

Translate »