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


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

Айналдыру тізімін бұру проблемасы бізге байланысты тізімді және бүтін санды ұсынады. Байланыстырылған тізімді оң жаққа 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 шешіміне арналған тәсіл

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

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