סובב את פתרון ה- Leetcode ברשימה


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית בלומברג פייסבוק לינקדין מיקרוסופט סמסונג
רשימה מקושרת שתי מצביעים

הבעיה פיתרון רשימת סובב רישום מאפשר לנו רשימה מקושרת ומספר שלם. נאמר לנו לסובב את הרשימה המקושרת ימינה לפי 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]. ומכאן התשובה.

head = [0,1,2], k = 4
[2, 0, 1]

הסבר: חזרה על התהליך 4 פעמים גורמת לרשימת קישור התשובות. ניתן להבין זאת טוב יותר על ידי התבוננות בתמונה למטה.

סובב את פתרון ה- Leetcode ברשימה

גישה לפיתרון רשימת סיבוב רוטציה

הבעיה פיתרון רשימת סובב רשימת קוד מציין כי ניתנת לך רשימה מקושרת עם מספר שלם לסיבוב. פירוש הדבר שעלינו לסובב את הרשימה ש- k ממקמת ימינה. ניתן להבין את הבעיה על ידי פעולה פשוטה של ​​לקיחת האלמנטים מסוף הרשימה והצבתם לפניהם. מכיוון שאין דרך להסיר ביעילות אלמנט מהקצה ולהציב אותו לפניו. עלינו לחשוב על כל דרך אחרת לבצע את הפעולה. אם נצפה, נוכל לראות שלאחר ביצוע פעולות k, אלמנטים k מהסוף מוסרים ומונחים מלפנים. דבר אחד שיש לציין כאן הוא, אם גודל k גדול מגודל הרשימה המקושרת. ניקח את המודול של k לאורך הרשימה המקושרת.

לאחר שתסיים, נעבור עד לצומת kth מהסוף. ואז אנו מבצעים חלק מהפעולות, אנו מקצים את הצומת הבא של הראש לראש. הקצה את הצומת kth מהקצה כראש הרשימה המקושרת. אך אל לנו לשכוח להקצות את הצומת הבא של הצומת k-1 מהסוף לסוף null. כעת, לאחר ביצוע שלוש הפעולות הללו, החלפנו את הרשימה.

קוד לפיתרון רשימת סיבוב

קוד 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

קוד Java

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

ניתוח מורכבות

מורכבות זמן

O (N) כאשר N מייצג את גודל הרשימה המקושרת. מכיוון שעלינו לחצות את הרשימה המקושרת, מורכבות הזמן היא לינארית ותלויה בגודל הרשימה.

מורכבות בחלל

O (1), מכיוון שאיננו צריכים לאחסן מידע עבור כל אחד מהצמתים. לפיכך, מורכבות החלל היא קבועה.