सूची लिटकोड समाधान घुमाएँ  


कठिनाई स्तर मध्यम
में अक्सर पूछा एडोब वीरांगना ब्लूमबर्ग Facebook लिंक्डइन माइक्रोसॉफ्ट सैमसंग
एल्गोरिदम कोडिंग साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस लिंक्ड सूची दो संकेत

समस्या रोटेट लिस्ट लेटकोड सॉल्यूशन हमें एक लिंक्ड लिस्ट और एक पूर्णांक प्रदान करता है। हमें लिंक की गई सूची को 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 बार दोहराने से। नीचे दी गई छवि को देखकर इसे बेहतर तरीके से समझा जा सकता है।

सूची लिटकोड समाधान घुमाएँपिन

Rotate List Leetcode Solution के लिए दृष्टिकोण  

समस्या रोटेट लिस्ट लेटकोड सॉल्यूशन बताता है कि आपको रोटेशन के लिए एक पूर्णांक के साथ एक लिंक्ड लिस्ट दी गई है। इसका मतलब है कि हमें सूची k स्थानों को दाईं ओर घुमाने की आवश्यकता है। सूची के अंत से तत्वों को लेने और उन्हें सामने रखने के एक सरल ऑपरेशन से समस्या को समझा जा सकता है। चूंकि कोई रास्ता नहीं है कुशलता एक तत्व को अंत से हटाकर सामने रख दें। हमें ऑपरेशन करने के किसी अन्य तरीके के बारे में सोचने की जरूरत है। यदि हम ध्यान दें, तो हम देख सकते हैं कि k ऑपरेशन करने के बाद, k तत्वों को अंत से हटा दिया जाता है और सामने रखा जाता है। यहाँ एक बात ध्यान देने योग्य है, यदि k का आकार, the के आकार से बड़ा है लिंक्ड सूची. हम की लंबाई के ऊपर k का मापांक लेंगे लिंक्ड सूची.

यह भी देखें
बाइनरी सर्च ट्री में न्यूनतम मान के साथ नोड खोजें

एक बार हो जाने के बाद, हम तब तक यात्रा करेंगे जब तक अंत से kth नोड. फिर हम कुछ ऑपरेशन करते हैं, हम अंतिम नोड के अगले सिर को असाइन करते हैं। लिंक की गई सूची के प्रमुख के रूप में अंत से kth नोड असाइन करें। लेकिन हमें 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

जावा कोड

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), चूंकि हमें प्रत्येक नोड के लिए जानकारी संग्रहीत करने की आवश्यकता नहीं है। इस प्रकार, अंतरिक्ष जटिलता निरंतर है।

1