Ротирајте листу Леетцоде Солутион


Ниво тешкоће Средњи
Често питани у адобе амазонка Блоомберг фацебоок ЛинкедИн мицрософт самсунг
Повезана листа Тво Поинтерс

Проблем Ротате Лист Леетцоде Солутион пружа нам повезану листу и цео број. Речено нам је да повезану листу ротирамо удесно за к места. Дакле, ако ротирамо повезану листу к места удесно, у сваком кораку узимамо последњи елемент са листе и смештамо је из. Понављамо ово док не обавимо к број ових операција. Погледајмо неколико примера.

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 пута доводи до листе повезаних са одговорима. То се може боље разумети гледањем слике испод.

Ротирајте листу Леетцоде Солутион

Приступ решењем са ротацијским списком Леетцоде

Проблем Ротате Лист Леетцоде Солутион наводи да сте добили повезану листу са целим бројем за ротацију. То значи да морамо да ротирамо листу к места удесно. Проблем се може разумети једноставном операцијом узимања елемената са краја листе и постављања испред. Пошто не постоји начин да се елемент ефикасно уклони са краја и постави испред. Морамо смислити било који други начин за извођење операције. Ако посматрамо, можемо видети да се након извођења к операција к елементи са краја уклањају и постављају испред. Овде треба приметити једну ствар, ако је величина к већа од величине повезане листе. Узећемо модул к за дужину повезане листе.

Када завршимо, кретаћемо се до краја к-тог чвора. Затим изводимо неке од операција, додељујемо следећи последњи чвор глави. Додијелите к-том чвору с краја као главу повезане листе. Али не треба заборавити доделити следећи чвор к-1-ог чвора с краја нули. Сада, након извођења ове 3 операције, ротирали смо листу.

Код за решење ротационе листе Леетцоде решење

Ц ++ код

#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

Јава Цоде

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

Анализа сложености

Сложеност времена

НА), где Н представља величину повезане листе. Будући да морамо прећи повезану листу, временска сложеност је линеарна и зависи од величине листе.

Сложеност простора

О (1), пошто не треба да складиштимо информације за сваки од чворова. Дакле, сложеност простора је константна.