ලැයිස්තු ලීට්කෝඩ් විසඳුම කරකවන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් බ්ලූම්බර්ග් ෆේස්බුක් LinkedIn මයික්රොසොෆ්ට් Samsung ජංගම දුරකථන
සම්බන්ධිත ලැයිස්තුව පොයින්ටර් දෙකක්

භ්‍රමණය වන ලැයිස්තුව ලීට්කෝඩ් විසඳුම අපට සම්බන්ධිත ලැයිස්තුවක් සහ පූර්ණ සංඛ්‍යාවක් සපයයි. සම්බන්ධිත ලැයිස්තුව 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 වතාවක් පුනරාවර්තනය කිරීමෙන් පිළිතුරු සම්බන්ධිත ලැයිස්තුවට හේතු වේ. පහත රූපය දෙස බැලීමෙන් එය වඩාත් හොඳින් වටහා ගත හැකිය.

ලැයිස්තු ලීට්කෝඩ් විසඳුම කරකවන්න

භ්‍රමණය වන ලැයිස්තු ලීට්කෝඩ් විසඳුම සඳහා ප්‍රවේශය

භ්‍රමණය වන ලැයිස්තුව ලීට්කෝඩ් විසඳුමේ සඳහන් වන්නේ භ්‍රමණය සඳහා පූර්ණ සංඛ්‍යාවක් සමඟ සම්බන්ධිත ලැයිස්තුවක් ඔබට ලබා දී ඇති බවයි. මෙයින් අදහස් කරන්නේ අපි k ස්ථාන ලැයිස්තුව දකුණට කරකැවිය යුතු බවයි. ලැයිස්තුවේ කෙළවරේ සිට මූලද්‍රව්‍ය ගෙන ඒවා ඉදිරියෙන් තැබීමේ සරල මෙහෙයුමකින් ගැටළුව තේරුම් ගත හැකිය. මූලද්‍රව්‍යයක් කෙළවරින් කාර්යක්ෂමව ඉවත් කර ඉදිරියෙන් තැබීමට ක්‍රමයක් නොමැති බැවින්. මෙහෙයුම සිදු කිරීම සඳහා වෙනත් ක්‍රමයක් ගැන අප සිතිය යුතුය. අප නිරීක්ෂණය කළහොත්, k මෙහෙයුම් සිදු කිරීමෙන් පසු, කෙළවරේ k මූලද්‍රව්‍ය ඉවත් කර ඉදිරියෙන් තබා ඇති බව අපට පෙනේ. මෙහිදී සටහන් කළ යුතු එක් දෙයක් නම්, k හි ප්‍රමාණය සම්බන්ධිත ලැයිස්තුවේ ප්‍රමාණයට වඩා වැඩි නම්. සම්බන්ධිත ලැයිස්තුවේ දිගට වඩා k හි මොඩියුලය අපි ගනිමු.

එය අවසන් වූ පසු, අපි අවසානයේ සිට kth node එක දක්වා ගමන් කරමු. ඉන්පසු අපි සමහර මෙහෙයුම් සිදු කරන්නෙමු, අපි අවසාන නෝඩයේ ඊළඟ කොටස හිසට පවරමු. සම්බන්ධිත ලැයිස්තුවේ ප්‍රධානියා ලෙස අවසානයේ සිට kth node එක යොදන්න. නමුත් 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), එක් එක් නෝඩ් සඳහා තොරතුරු ගබඩා කිරීමට අපට අවශ්‍ය නැති නිසා. මේ අනුව, අභ්‍යවකාශ සංකීර්ණතාව නියත ය.