Պտտեցնել ցուցակը Leetcode լուծում


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Amazon Bloomberg facebook LinkedIn Microsoft Samsung
Կապված ցուցակ Երկու ցուցիչ

Rotate List Leetcode Solution- ի խնդիրը մեզ կապակցված ցուցակ և ամբողջ թիվ է տալիս: Մեզ ասում են, որ կապակցված ցուցակը պտտեցրեք աջ ՝ ըստ 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 լուծման մոտեցումը

Rotate List Leetcode Solution- ի խնդիրը նշում է, որ պտտման համար ձեզ տրվում է կապված ցուցակ `ամբողջ թվով: Սա նշանակում է, որ պետք է պտտեցնել ցուցակը k տեղերը աջ: Խնդիրը կարելի է հասկանալ ցուցակի վերջից տարրերը հանելու և դրանց դիմաց տեղադրելու պարզ գործողությամբ: Քանի որ ոչ մի կերպ չի հաջողվում արդյունավետորեն տարրը հեռացնել վերջից և տեղադրել այն առջևում: Մենք պետք է մտածենք վիրահատությունը կատարելու ցանկացած այլ եղանակի մասին: Եթե ​​դիտարկենք, կտեսնենք, որ k գործողություններ կատարելուց հետո վերջից k տարրերը հանվում և տեղադրվում են առջևում: Այստեղ պետք է նշել մի բան, եթե k- ի չափը մեծ է կապված ցուցակի չափից: K- ի մոդուլը կվերցնենք կապված ցուցակի երկարության վրա:

Ավարտելուց հետո մենք անցնելու ենք մինչև վերջի հանգույցը: Դրանից հետո մենք կատարում ենք գործողությունների մի մասը, վերջին հանգույցի հաջորդը վերագրում ենք գլխին: Վերադարձի հանգույցը վերագրեք որպես կապակցված ցուցակի ղեկավար: Բայց չպետք է մոռանանք k-1-ին հանգույցի հաջորդ հանգույցին վերջից անվանական նշանակելը: Այժմ, այս 3 գործողությունները կատարելուց հետո, մենք պտտել ենք ցուցակը:

Պտտման ցուցակի Leetcode լուծման կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), որտեղ N- ը ներկայացնում է կապված ցուցակի չափը: Քանի որ մենք պետք է անցնենք կապված ցուցակը, ժամանակի բարդությունը գծային է և կախված է ցուցակի չափից:

Տիեզերական բարդություն

O (1), քանի որ մեզ անհրաժեշտ չէ յուրաքանչյուր հանգույցի համար տեղեկատվություն պահել: Այսպիսով, տարածության բարդությունը կայուն է: