Kth Düyünü əvvəldən Kth Node ilə End-dən dəyişdirin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon BlackRock Morgan Stanley
Bağlı siyahı Əlaqəli siyahı RockstandBaxılıb 323

Problem bəyanat

“Kth Node'u sonundan Kth Node ilə dəyişdirin” problemində, a əlaqəli siyahı. Kth düyünü əvvəldən və kth node ilə sondan dəyişdirin. Dəyərləri dəyişdirməliyik, göstəriciləri dəyişdirməliyik.

misal

2
1 2 3 4 5 6
1 5 3 4 2 6

Yanaşma

Bağlı bir siyahı və bir k dəyəri nəzərə alaraq, kth node dəyərlərini başlanğıcdan və kth node'u sonundan dəyişdirməliyik. Bağlı siyahının uzunluğunu bilmirik, yalnız k dəyərini bilirik.

Uzunluğu bilmədiyimiz üçün uzunluğu tapmaq üçün əlaqəli siyahıya təkrarlamalıyıq. Və kth nodu saxlayırıq və ikinci təkrarlamada, kth nodu sonundan, yəni n-əlaqəli siyahının uzunluğu olduğu n-kth nodu tapa bilərik. Və ya sualda verilmiş məlumatlardan istifadə edə bilərik, kth düyününün ucundan məsafəsi ucdan olan məsafəyə bərabərdir. Bu metodla əlaqəli siyahının uzunluğunu tapmaq lazım deyil.

Pin

Əvvəlcə başı göstərən bir cərəyan göstəricisi alırıq, sonra bu göstəricini kth düyününə aparırıq.  İki göstərici p1 və p2 götürün, p1 baş düyünə, p2 isə döngə -> sonrakı nöqtələrə. Nümunə olaraq şəkildə yuxarıdakı əlaqəli siyahını götürsək, p1 dəyəri 1 ilə pode, 2 dəyəri olan nodu göstərir.

Sonra p1 göstəricisi sıfırlanana qədər həm p2 həm də p2 göstəricilərini təkrarlayın və əlaqəli siyahının sonuna çatırıq. Sonra p1 ucundan kth nodu göstərir və curth göstəricisində saxlanılan kth-node var. Düyünlərdəki dəyərləri dəyişdiririk.

Həyata keçirilməsi

Kth Düyünü End'dən Kth Düyünü ilə əvvəldən dəyişdirmə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 swapNodes(int k) {
        int len=0;
        ListNode* curr = head;
        for(int i=1;i<k;i++){
            curr = curr->next;
        }
        ListNode* p1 = head,*p2 = curr->next;
        while(p2){
            p1 = p1->next;
            p2=p2->next;
        }
        swap(curr->val,p1->val);
    }

    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->swapNodes(2);
    list->print_list();
}

Kth Node'u əvvəldən End'dən Kth Node ilə dəyişdirmək üçü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.swapNodes(2);
    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 swapNodes(int k) {
          Node A = head, B = head, nodeK;
          for (int i = 1; i < k; i++) A = A.next;
          nodeK = A;
          A = A.next;
          while (A != null) {
              A = A.next;
              B = B.next;
          }
          int temp = nodeK.val;
          nodeK.val = B.val;
          B.val = temp;
          
    }

    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 4 3 2 5

Kth Düyünü əvvəldən Kth Node ilə End-dən dəyişdirmək üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

Tamam) hara k girişin özündə verilmiş tam dəyərdir.

Kosmik Mürəkkəblik

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

Translate »