பட்டியல் லீட்கோட் தீர்வை சுழற்று


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ப்ளூம்பெர்க் பேஸ்புக் லின்க்டு இன் மைக்ரோசாப்ட் சாம்சங்
இணைக்கப்பட்ட பட்டியல் இரண்டு சுட்டிகள்

சுழற்று பட்டியல் லீட்கோட் தீர்வு எங்களுக்கு இணைக்கப்பட்ட பட்டியலையும் ஒரு முழு எண்ணையும் வழங்குகிறது. இணைக்கப்பட்ட பட்டியலை 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 முறை மீண்டும் செய்வது பதில் இணைக்கப்பட்ட பட்டியலில் விளைகிறது. கீழே உள்ள படத்தைப் பார்ப்பதன் மூலம் இதை நன்கு புரிந்து கொள்ள முடியும்.

பட்டியல் லீட்கோட் தீர்வை சுழற்று

சுழற்று பட்டியல் லீட்கோட் தீர்வுக்கான அணுகுமுறை

சுழற்று பட்டியல் லீட்கோட் தீர்வு சுழற்சிக்கான முழு எண்ணுடன் இணைக்கப்பட்ட பட்டியல் உங்களுக்கு வழங்கப்பட்டுள்ளது என்று கூறுகிறது. இதன் பொருள் நாம் கே இடங்களை வலதுபுறமாக சுழற்ற வேண்டும். பட்டியலின் முடிவில் இருந்து உறுப்புகளை எடுத்து அவற்றை முன் வைப்பதன் எளிய செயல்பாட்டின் மூலம் சிக்கலைப் புரிந்து கொள்ள முடியும். ஒரு உறுப்பை முடிவில் இருந்து திறம்பட அகற்றி அதை முன் வைக்க வழி இல்லை என்பதால். செயல்பாட்டைச் செய்ய வேறு எந்த வழியையும் நாம் சிந்திக்க வேண்டும். நாம் கவனித்தால், k செயல்பாடுகளைச் செய்தபின், முடிவில் இருந்து k கூறுகள் அகற்றப்பட்டு முன்னால் வைக்கப்படுவதைக் காணலாம். இங்கே கவனிக்க வேண்டிய ஒரு விஷயம் என்னவென்றால், இணைக்கப்பட்ட பட்டியலின் அளவை விட k இன் அளவு அதிகமாக இருந்தால். இணைக்கப்பட்ட பட்டியலின் நீளத்திற்கு மேல் k இன் மட்டு எடுப்போம்.

முடிந்ததும், முடிவில் இருந்து kth முனை வரை பயணிப்போம். பின்னர் நாங்கள் சில செயல்பாடுகளைச் செய்கிறோம், கடைசி முனையின் அடுத்ததை தலைக்கு ஒதுக்குகிறோம். இணைக்கப்பட்ட பட்டியலின் தலைவராக இறுதியில் இருந்து kth முனையை ஒதுக்கவும். ஆனால் k-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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), இணைக்கப்பட்ட பட்டியலின் அளவை N குறிக்கிறது. இணைக்கப்பட்ட பட்டியலை நாம் பயணிக்க வேண்டியிருப்பதால், நேர சிக்கலானது நேரியல் மற்றும் பட்டியலின் அளவைப் பொறுத்தது.

விண்வெளி சிக்கலானது

ஓ (1), ஒவ்வொரு முனைகளுக்கும் நாங்கள் தகவல்களை சேமிக்க தேவையில்லை என்பதால். இதனால், விண்வெளி சிக்கலானது நிலையானது.