പട്ടിക ലീറ്റ്കോഡ് പരിഹാരം തിരിക്കുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ബ്ലൂംബർഗ് ഫേസ്ബുക്ക് ലിങ്ക്ഡ് മൈക്രോസോഫ്റ്റ് സാംസങ്
ലിങ്ക്ഡ്-ലിസ്റ്റ് രണ്ട് പോയിന്ററുകൾ

റൊട്ടേറ്റ് ലിസ്റ്റ് ലീറ്റ്കോഡ് പരിഹാരം ഞങ്ങൾക്ക് ഒരു ലിങ്കുചെയ്‌ത ലിസ്റ്റും ഒരു സംഖ്യയും നൽകുന്നു. കെ സ്ഥലങ്ങൾ ഉപയോഗിച്ച് ലിങ്കുചെയ്‌ത ലിസ്റ്റ് വലത്തേക്ക് തിരിക്കാൻ ഞങ്ങളോട് പറയുന്നു. അതിനാൽ ഞങ്ങൾ ഒരു ലിങ്കുചെയ്‌ത ലിസ്റ്റ് കെ സ്ഥലങ്ങൾ വലത്തേക്ക് തിരിക്കുകയാണെങ്കിൽ, ഓരോ ഘട്ടത്തിലും ഞങ്ങൾ പട്ടികയിൽ നിന്ന് അവസാന ഘടകം എടുത്ത് അതിൽ നിന്ന് സ്ഥാപിക്കുന്നു. ഈ പ്രവർത്തനങ്ങളുടെ 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 തവണ ആവർത്തിക്കുന്നത് ഉത്തരം ലിങ്കുചെയ്ത പട്ടികയിൽ കലാശിക്കും. ചുവടെയുള്ള ചിത്രം നോക്കിയാൽ ഇത് നന്നായി മനസ്സിലാക്കാൻ കഴിയും.

പട്ടിക ലീറ്റ്കോഡ് പരിഹാരം തിരിക്കുക

റൊട്ടേറ്റ് ലിസ്റ്റ് ലീറ്റ്കോഡ് പരിഹാരത്തിനുള്ള സമീപനം

റൊട്ടേറ്റ് ലിസ്റ്റ് ലീറ്റ്കോഡ് സൊല്യൂഷൻ, റൊട്ടേഷനായി ഒരു പൂർണ്ണസംഖ്യയുള്ള ഒരു ലിങ്ക്ഡ് ലിസ്റ്റ് നിങ്ങൾക്ക് നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. ഇതിനർത്ഥം k സ്ഥലങ്ങൾ വലതുവശത്തേക്ക് തിരിക്കേണ്ടതുണ്ട് എന്നാണ്. ലിസ്റ്റിന്റെ അവസാനഭാഗത്ത് നിന്ന് ഘടകങ്ങൾ എടുത്ത് അവയെ മുന്നിൽ വയ്ക്കുന്ന ലളിതമായ പ്രവർത്തനത്തിലൂടെ പ്രശ്നം മനസ്സിലാക്കാൻ കഴിയും. ഒരു മൂലകം അറ്റത്ത് നിന്ന് കാര്യക്ഷമമായി നീക്കംചെയ്ത് മുന്നിൽ വയ്ക്കാൻ ഒരു മാർഗവുമില്ലാത്തതിനാൽ. പ്രവർത്തനം നടത്താൻ മറ്റെന്തെങ്കിലും മാർഗത്തെക്കുറിച്ച് നമ്മൾ ചിന്തിക്കേണ്ടതുണ്ട്. നമ്മൾ നിരീക്ഷിക്കുകയാണെങ്കിൽ, k പ്രവർത്തനങ്ങൾ നടത്തിയ ശേഷം, അവസാനം നിന്നുള്ള k ഘടകങ്ങൾ നീക്കംചെയ്യുകയും അവ മുന്നിൽ സ്ഥാപിക്കുകയും ചെയ്യുന്നു. ഇവിടെ ശ്രദ്ധിക്കേണ്ട ഒരു കാര്യം, കെ യുടെ വലുപ്പം ലിങ്കുചെയ്ത പട്ടികയുടെ വലുപ്പത്തേക്കാൾ വലുതാണെങ്കിൽ. ലിങ്കുചെയ്‌ത ലിസ്റ്റിന്റെ ദൈർഘ്യത്തെക്കാൾ k ന്റെ മൊഡ്യൂൾ ഞങ്ങൾ എടുക്കും.

പൂർത്തിയാക്കിക്കഴിഞ്ഞാൽ, അവസാനം മുതൽ kth നോഡ് വരെ ഞങ്ങൾ സഞ്ചരിക്കും. തുടർന്ന് ഞങ്ങൾ ചില പ്രവർത്തനങ്ങൾ നടത്തുന്നു, അവസാന നോഡിന്റെ അടുത്തത് ഞങ്ങൾ തലയ്ക്ക് നൽകുന്നു. ലിങ്കുചെയ്‌ത ലിസ്റ്റിന്റെ തലയായി അവസാനം മുതൽ kth നോഡ് നൽകുക. K-1 th നോഡിന്റെ അടുത്ത നോഡ് അവസാനം മുതൽ ശൂന്യമായി നൽകുന്നത് ഞങ്ങൾ മറക്കരുത്. ഇപ്പോൾ, ഈ 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), ഇവിടെ N ലിങ്കുചെയ്‌ത ലിസ്റ്റിന്റെ വലുപ്പത്തെ പ്രതിനിധീകരിക്കുന്നു. ഞങ്ങൾ‌ ലിങ്കുചെയ്‌ത പട്ടികയിലൂടെ സഞ്ചരിക്കേണ്ടതിനാൽ‌, സമയ സങ്കീർ‌ണ്ണത രേഖീയവും പട്ടികയുടെ വലുപ്പത്തെ ആശ്രയിച്ചിരിക്കുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), കാരണം ഓരോ നോഡിനും വിവരങ്ങൾ സംഭരിക്കേണ്ടതില്ല. അതിനാൽ, സ്പേസ് സങ്കീർണ്ണത സ്ഥിരമാണ്.