لسٽ ليٽ ڪوڊ حل گھمڻ


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ ايڊوب Amazon Bloomberg ڪريو LinkedIn، Microsoft جي سنگ
ڳن -يل فهرست ٻه اشارو

مسئلو روٽ لسٽ ليوٽ ڪوڊ حل اسان کي ڳن listيل لسٽ ۽ انٽيگر مهيا ڪري ٿو. اسان کي ٻڌايو ويو آهي ته ڳن placesيل لسٽن کي درست ڪن ٿا ڪن جڳھن کان. ان ڪري جيڪڏهن اسان ڳن listيل فهرست ڪي جڳهيون سا theي طرف گھمائيندا ، هر قدم ۾ اسان لسٽ مان آخري عنصر رکون ٿا ۽ ان ۾ رکيا آهيون. اسين هن کي ٻيهر ورجائيندا رهون ٿا جيستائين اسان هنن آپريشنن جو ڪل نمبر نه ڪيو آهي. اچو ته ڪجھ مثالن تي نظر وجهون.

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 ڀيرا ورجائڻ جو نتيجو جواب ۾ ڳن linkedيل لسٽ ۾. هيٺ ڏنل تصوير کي ڏسي ڏسي اهو بهتر سمجهي سگهجي ٿو.

لسٽ ليٽ ڪوڊ حل گھمڻ

گردش لسٽ ليٽ ڪوڊ جو حل

مسئلو Rotate List Leetcode Solution ٻڌائي ٿو ته توهان کي گردش لاءِ هڪ عدد هڪ وڏي فهرست ڏني وئي آهي. هن جو مطلب آهي ته اسان کي فهرست ڪي جڳھون گھڙي گھمائڻ گھرجن. ان مسئلي کي لسٽ جي پڇاڙي کان وٺي ۽ ان کي اڳيان رکڻ جي آسان آپريشن مان سمجهي سگهجي ٿو. جتان ڪنهن به عنصر کي موثر طور تي ختم کان ختم ڪرڻ ۽ ان کي اڳيان ۾ رکڻ جو ڪو طريقو ناهي. اسان کي آپريشن ڪرڻ لاءِ ڪنهن ٻئي طريقي بابت سوچڻ گهرجي. جيڪڏهن اسان مشاهدو ڪيون ، اسان ڏسي سگھون ٿا ته ڪ آپريشن ڪرڻ کان پوءِ ، ڪي جا عنصر آخر کان ڪ areيا وڃن ٿا ۽ اڳيان رکيل آهن. هڪ ڳالهه ۽ هتي ڌيان ڏيڻ اها آهي ، جيڪڏهن ڪ جي ڳن linkedيل ڳن listيل فهرست جي سائز کان وڌيڪ هجي. اسان ڳن linked واري فهرست جي ڊيگهه تي ڪ جي ماڊلولو کڻي وينداسين.

هڪ دفعو مڪمل ٿي ويندو ، اسان آخر تائين ڪيٿ نوڊ تائين لڌل ڏينداسين. ان کان پوء اسان ڪجھ عمل ڪيو ، اسان آخري نوڊ جي اڳيان سر کي لڳايو ٿا. لنڪ لسٽ جي سربراهي طور ڪيٿ نوڊ آخر کان لڳايو. پر اسان کي ڪي-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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، جتي اين لنڪ لسٽ جي سائيز جي نمائندگي ڪري ٿو. جئين اسان کي ڳن listيل فهرست مان ڳولڻو آهي ، ان وقت جي پيچيدگي لڪير جي آهي ۽ فهرست جي شڪل تي منحصر آهي.

خلائي پيچيدگي

اي (1) ، اسان کي هر هڪ نوڊس جي معلومات اسٽور ڪرڻ جي ضرورت ناهي. ان ڪري ، خلا جي پيچيدگي مستقل آهي.