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


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

समस्या घुमाएँ सूची Leetcode समाधान हमें एक लिंक्ड सूची और एक पूर्णांक प्रदान करता है। हमें कहा गया है कि लिंक किए गए सूची को 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 के लिए दृष्टिकोण

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

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