ಪಟ್ಟಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ತಿರುಗಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಫೇಸ್ಬುಕ್ ಸಂದೇಶ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಸ್ಯಾಮ್ಸಂಗ್
ಲಿಂಕ್ಡ್-ಲಿಸ್ಟ್ ಎರಡು ಪಾಯಿಂಟರ್‌ಗಳು

ತಿರುಗುವ ಪಟ್ಟಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ನಮಗೆ ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿ ಮತ್ತು ಪೂರ್ಣಾಂಕವನ್ನು ಒದಗಿಸುತ್ತದೆ. ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಯನ್ನು ಕೆ ಸ್ಥಳಗಳಿಂದ ಬಲಕ್ಕೆ ತಿರುಗಿಸಲು ನಮಗೆ ತಿಳಿಸಲಾಗಿದೆ. ಆದ್ದರಿಂದ ನಾವು ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿ ಕೆ ಸ್ಥಳಗಳನ್ನು ಬಲಕ್ಕೆ ತಿರುಗಿಸಿದರೆ, ಪ್ರತಿ ಹಂತದಲ್ಲೂ ನಾವು ಪಟ್ಟಿಯಿಂದ ಕೊನೆಯ ಅಂಶವನ್ನು ತೆಗೆದುಕೊಂಡು ಅದನ್ನು ಇಡುತ್ತೇವೆ. ಈ ಕಾರ್ಯಾಚರಣೆಗಳ ಕೆ ಸಂಖ್ಯೆಯನ್ನು ಮಾಡುವವರೆಗೆ ನಾವು ಇದನ್ನು ಪುನರಾವರ್ತಿಸುತ್ತೇವೆ. ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ನೋಡೋಣ.

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 ನ ಗಾತ್ರವು ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಯ ಗಾತ್ರಕ್ಕಿಂತ ಹೆಚ್ಚಿದ್ದರೆ. ಲಿಂಕ್ ಮಾಡಲಾದ ಪಟ್ಟಿಯ ಉದ್ದಕ್ಕೂ ನಾವು ಕೆ ನ ಮಾಡ್ಯುಲೋವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತೇವೆ.

ಒಮ್ಮೆ ಮಾಡಿದ ನಂತರ, ನಾವು ಕೊನೆಯಿಂದ 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), ಪ್ರತಿಯೊಂದು ನೋಡ್‌ಗಳಿಗೆ ನಾವು ಮಾಹಿತಿಯನ್ನು ಸಂಗ್ರಹಿಸುವ ಅಗತ್ಯವಿಲ್ಲ. ಹೀಗಾಗಿ, ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ.