Парақ кодының тізімін бұру  


Күрделілік дәрежесі орта
Жиі кіреді Adobe Amazon Bloomberg Facebook LinkedIn Microsoft Samsung
алгоритмдер кодтау сұхбат сұхбат дайындау LeetCode LeetCodeSolutions Байланыстырылған тізім Екі нұсқағыш

Leetcode шешімінің тізімін бұру мәселесі бізге байланыстырылған тізім мен бүтін санды ұсынады. Бізге байланыстырылған тізімді оң жаққа k орын бойынша бұру керек дейді. Егер біз байланыстырылған тізімді k орынға оңға бұрсақ, әр қадамда біз тізімнен соңғы элементті алып, оны орналастырамыз. Біз қайталау бұл біз осы операциялардың 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 рет қайталау нәтижесінде жауаптар тізімі шығады. Оны төмендегі суретке қарап жақсы түсінуге болады.

Парақ кодының тізімін бұрутүйреуіш

Айналмалы тізімнің Leetcode шешіміне арналған тәсіл  

Leetcode Solution тізімін айналдыру мәселесі сізге айналу үшін бүтін санмен байланыстырылған тізім берілгенін айтады. Бұл k орындар тізімін оңға бұру керек дегенді білдіреді. Тізімнің соңындағы элементтерді алып, оларды алдына қоюдың қарапайым операциясымен мәселені түсінуге болады. Себебі амал жоқ тиімді элементті соңынан алып тастап, алдына қойыңыз. Біз операцияны орындаудың басқа жолын ойлауымыз керек. Егер бақылайтын болсақ, онда k амалдарын орындағаннан кейін, соңынан k элементтері алынып, олардың алдына қойылатынын көреміз. Мұнда назар аударатын бір нәрсе, егер k өлшемі байланыстырылған тізім. Біз k модулін ұзындығы бойынша аламыз байланыстырылған тізім.

Сондай-ақ, қараңыз
Екілік іздеу ағашында минималды мәні бар түйінді табыңыз

Аяқтағаннан кейін біз жолға шығамыз аяғынан бастап 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

Күрделілікті талдау  

Уақыттың күрделілігі

O (N), Мұндағы N байланыстырылған тізімнің өлшемін білдіреді. Байланысты тізімді өту керек болғандықтан, уақыттың күрделілігі сызықтық болып табылады және тізім өлшеміне тәуелді болады.

Сондай-ақ, қараңыз
Изоморфты тізбектер лист кодының шешімі

Ғарыштың күрделілігі

O (1), өйткені әр түйін үшін ақпаратты сақтаудың қажеті жоқ. Осылайша, ғарыштық Күрделілік тұрақты болып табылады.

1