דרייען רשימה לעעטקאָדע סאַלושאַן  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַדאָובי אַמאַזאָן בלומבערג facebook לינקעדין מייקראָסאָפֿט סאַמסונג
אַלגערידאַמז קאָדירונג אינטערוויו interviewprep LeetCode LeetCodeSolutions לינקעד-רשימה צוויי פּאָינטערס

דער פּראָבלעם דרייען ליסטע לעעטקאָדע סאַלושאַן גיט אונדז אַ לינגקט רשימה און אַ ינטאַדזשער. מיר זענען געזאָגט צו דרייען די לינגקט רשימה צו די רעכט דורך k ערטער. אויב מיר דרייען אַ לינגקט רשימה ק ערטער צו די רעכט, אין יעדער שריט מיר נעמען די לעצטע עלעמענט פֿון דער רשימה און שטעלן עס פֿון. מיר יבערכאַזערן דעם ביז מיר האָבן דורכגעקאָכט די נומער פון די אַפּעריישאַנז. זאל ס נעמען אַ קוק בייַ אַ ביסל ביישפילן.

head = [1,2,3,4,5], k = 2
[4,5,1,2,3]

דערקלערונג: לאָמיר די אָפּעראַציע צעטיילן אין 2 פּשוט ראָוטיישאַן אַפּעריישאַנז אַזוי, אין דער ערשטער שריט אָדער מאַך, מיר נאָר נעמען דעם עלעמענט פֿון דער סוף פון דער רשימה און שטעלן אים אין פראָנט. אַזוי, די רשימה ווערט [5, 1, 2, 3, 4]. איצט מיר ווידער איבערחזרן די זעלבע אָפּעראַציע פון ​​די רשימה, [4, 5, 1, 2, 3]. דערפאר די ענטפער.

head = [0,1,2], k = 4
[2, 0, 1]

דערקלערונג: ריפּיטינג דעם פּראָצעס 4 מאָל רעזולטאַט אין דער ענטפֿערן לינק רשימה. עס קען זיין בעסער פארשטאנען דורך די בילד אונטן.

דרייען רשימה לעעטקאָדע סאַלושאַןשפּילקע

צוגאַנג פֿאַר דרייען רשימה לעעטקאָדע סאַלושאַן  

דער פּראָבלעם מיט דרייען ליסטע לעעטקאָדע סאַלושאַן דערקלערט אַז איר באַקומען אַ לינגקט רשימה מיט אַ ינטאַדזשער פֿאַר ראָוטיישאַן. דעם מיטל אַז מיר דאַרפֿן צו דרייען די רשימה ק ערטער צו די רעכט. דער פּראָבלעם קען זיין פארשטאנען דורך אַ פּשוט אָפּעראַציע צו נעמען די יסודות פון די סוף פון די רשימה און שטעלן זיי אין פראָנט. זינט עס איז קיין וועג צו עפפיסיענטלי אַראָפּנעמען אַן עלעמענט פון די סוף און שטעלן עס אין פראָנט. מיר דאַרפֿן צו טראַכטן וועגן קיין אנדערע וועג צו דורכפירן די אָפּעראַציע. אויב מיר אָבסערווירן, מיר קענען זען אַז נאָך דורכפירן ק אָפּעראַטיאָנס, ק עלעמענטן פון די סוף זענען אַוועקגענומען און זענען געשטעלט אין פראָנט. איין זאַך צו טאָן דאָ איז אויב די גרייס פון ק איז גרעסער ווי די גרייס פון דעם לינגקט רשימה. מיר נעמען די מאָדולאָ פון ק איבער די לענג פון די לינגקט רשימה.

זע אויך
געפֿינען די נאָדע מיט מינימום ווערט אין אַ ביינערי זוכן בוים

אַמאָל דאָס איז דורכגעקאָכט, מיר פאָרן ביז די kth נאָדע פֿון די סוף. דערנאָך מיר דורכפירן עטלעכע פון ​​די אַפּעריישאַנז, מיר באַשטימען דעם ווייַטער פון די לעצטע נאָדע צו די קאָפּ. באַשטימען די קטה נאָדע פֿון די סוף ווי די הויפּט פון די לינגקט רשימה. אָבער מיר זאָל נישט פאַרגעסן צו באַשטימען דעם ווייַטער נאָדע פון ​​ק -1 טה נאָדע פֿון די סוף ווי נאַל. איצט, נאָך דורכפירן די 3 אַפּעריישאַנז, מיר האָבן ראָוטייטיד די רשימה.

קאָד פֿאַר דרייען רשימה לעעטקאָדע סאַלושאַן  

C ++ קאָד

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

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

ListNode* rotateRight(ListNode* head, int k) {
    if(head==NULL || head->next==NULL)return head;

    ListNode *tmp = head;
    int cnt = 0;
    while(tmp)tmp=tmp->next,cnt++;
    tmp=head;
    k%=cnt;
    if(k==0)return head;

    while(k--)tmp = tmp->next;
    ListNode *tmpHead = head;
    while(tmp->next!=NULL){
        tmp = tmp->next;
        head = head->next;
    }
    ListNode* newHead = head->next;
    tmp->next = tmpHead;
    head->next = NULL;
    return newHead;
}

int main(){
    ListNode *head = new ListNode();
    head->data = 0;
    head->next = new ListNode();
    head->next->data = 1;
    head->next->next = new ListNode();
    head->next->next->data = 2;

    head = rotateRight(head, 4);
    while(head != NULL){
        cout<<head->data<<" ";
        head = head->next;
    }
}
2 0 1

Java קאוד

import java.util.*;
import java.lang.*;
import java.io.*;

class ListNode{
  int data;
  ListNode next;
}

class Solution {
    public static ListNode rotateRight(ListNode head, int k) {
        if(head==null || head.next==null)return head;
    
        ListNode tmp = head;
        int cnt = 0;
        while(tmp != null){
            tmp=tmp.next;
            cnt++;
        }
        tmp=head;
        k %= cnt;
        if(k==0)return head;

        while(k-- > 0)
            tmp = tmp.next;
        ListNode tmpHead = head;
        while(tmp.next != null){
            tmp = tmp.next;
            head = head.next;
        }
        ListNode newHead = head.next;
        tmp.next = tmpHead;
        head.next = null;
        return newHead;
    }
    
    public static void main(String[] args){
    	ListNode head = new ListNode();
      head.data = 0;
      head.next = new ListNode();
      head.next.data = 1;
      head.next.next = new ListNode();
      head.next.next.data = 2;
  
      head = rotateRight(head, 4);
      while(head != null){
          System.out.print(head.data + " ");
          head = head.next;
      }
    }
}
2 0 1

קאַמפּלעקסיטי אַנאַליסיס  

צייט קאַמפּלעקסיטי

אָ (N), וווּ N רעפּראַזענץ די גרייס פון די לינגקט רשימה. זינט מיר מוזן דורכגיין די לינגקט רשימה, די צייט קאַמפּלעקסיטי איז לינעאַר און איז אָפענגיק אויף די גרייס פון דער רשימה.

זע אויך
יסאָמאָרפיק סטרינגס לעעטקאָדע סאַלושאַן

ספעיס קאַמפּלעקסיטי

אָ (1), זינט מיר טאָן ניט דאַרפֿן צו קראָם אינפֿאָרמאַציע פֿאַר יעדער פון די נאָודז. אַזוי, פּלאַץ קאַמפּלעקסיטי איז קעסיידערדיק.

1