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


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

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

මෙයද බලන්න
ද්විමය සෙවුම් ගසක අවම අගයක් ඇති නෝඩය සොයා ගන්න

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

1