सूची लीटकोड सोल्यूशन फिरवा


अडचण पातळी मध्यम
वारंवार विचारले अडोब ऍमेझॉन ब्लूमबर्ग फेसबुक संलग्न मायक्रोसॉफ्ट सॅमसंग
दुवा साधलेली यादी दोन पॉईंटर्स

रोटेट यादी लीटकोड सोल्यूशन आम्हाला दुवा साधलेली यादी आणि पूर्णांक प्रदान करते. आम्हाला जोडलेल्या यादीला के ठिकाणी उजवीकडे फिरवण्यास सांगितले जाते. म्हणून जर आपण दुवा साधलेली यादी के स्थानांना उजवीकडे फिरवित असाल तर प्रत्येक चरणात आम्ही सूचीतून शेवटचा घटक घेतो आणि त्यामधून त्यात ठेवतो. आम्ही या ऑपरेशन्सची संख्या पूर्ण करेपर्यंत याची पुनरावृत्ती करतो. चला काही उदाहरणे पहा.

head = [1,2,3,4,5], k = 2
[4,5,1,2,3]

स्पष्टीकरणः ऑपरेशनला दोन सोप्या रोटेशन ऑपरेशन्समध्ये खंडित करूया. तर, पहिल्या चरणात किंवा हालचालीत आपण घटक सूचीच्या शेवटी घेतो आणि त्यास समोर ठेवतो. तर, यादी [2, 5, 1, 2, 3] होईल. आता पुन्हा आम्ही यादी बनवण्यासारख्या ऑपरेशनची पुनरावृत्ती करतो [4, 4, 5, 1, 2]. आणि म्हणून उत्तर.

head = [0,1,2], k = 4
[2, 0, 1]

स्पष्टीकरणः प्रक्रियेस 4 वेळा पुनरावृत्ती केल्याने उत्तर लिंक केलेल्या यादीमध्ये परिणाम होतो. खाली दिलेली प्रतिमा पाहून हे अधिक चांगल्या प्रकारे समजले जाऊ शकते.

सूची लीटकोड सोल्यूशन फिरवा

फिरवा यादी लीटकोड सोल्यूशनसाठी दृष्टिकोन

रोटेट यादी लीटकोड सोल्यूशनमध्ये म्हटले आहे की रोटेशनसाठी आपल्याला पूर्णांक असलेली जोडलेली यादी दिली आहे. याचा अर्थ असा की आपल्याला यादी स्थानांच्या उजवीकडे फिरविणे आवश्यक आहे. सूचीच्या शेवटी घटकांना समोर ठेवून आणि पुढे ठेवण्याच्या साध्या ऑपरेशनद्वारे ही समस्या समजू शकते. एखाद्या घटकाला शेवटपासून कार्यक्षमतेने काढण्याचा आणि समोर ठेवण्याचा कोणताही मार्ग नसल्यामुळे. ऑपरेशन करण्यासाठी इतर कोणत्याही मार्गाचा विचार करणे आवश्यक आहे. जर आपण निरिक्षण केले तर आपण पाहू शकतो की के ऑपरेशन्स केल्यावर, के घटक खाली केले जातात आणि समोर ठेवलेले असतात. येथे लक्षात घेण्याजोगी एक गोष्ट म्हणजे, जर केचा आकार जोडलेल्या यादीच्या आकारापेक्षा मोठा असेल तर. आम्ही जोडलेल्या यादीच्या लांबीवर के चे मॉड्यूल घेऊ.

एकदा झाल्यावर आम्ही kth नोडपर्यंत टोकापर्यंत जाऊ. मग आम्ही काही ऑपरेशन्स करतो, आम्ही शेवटच्या नोडच्या पुढील भागास डोके देतो. दुवा साधलेल्या यादीचा प्रमुख म्हणून शेवटी kth नोड नियुक्त करा. परंतु आम्ही के -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), आम्हाला प्रत्येक नोडसाठी माहिती संग्रहित करण्याची आवश्यकता नाही. अशा प्रकारे, स्पेस कॉम्प्लेक्सिटी स्थिर असते.