כתוב פונקציה כדי להשיג את נקודת הצומת של שתי רשימות מקושרות


רמת קושי קַל
נשאל לעתים קרובות נאמן אמזון בעברית דה שו סט עובדות גולדמן זאקס MakeMyTrip מאק מיקרוסופט קוואלקום Snapdeal וִיזָה זופר
רשימה מקושרת

הצהרת בעיה

הבעיה "כתוב פונקציה כדי להשיג את נקודת החיתוך של שתי רשימות מקושרות" קובעת שקיבלת שתי רשימות מקושרות. אך הן אינן רשימות מקושרות עצמאיות. הם מחוברים בשלב כלשהו. עכשיו אתה צריך למצוא את נקודת החיתוך הזו של שתי הרשימות האלה.

דוגמה

כתוב פונקציה כדי להשיג את נקודת הצומת של שתי רשימות מקושרות

1 -> 2
      \
        5 -> 6
      /
3 -> 4
Point of intersection: 5

הסבר: ישנן שתי רשימות מקושרות המוצגות בקלט שהן 1, 2, 5, 6 ו- 3, 4, 5, 6. שתיהן מוזגו בצומת שערכו 5. לפיכך הפלט הוא 5.

גישה

הבעיה פשוטה לתיאור. יש שני רשימות מקושרות אבל הם מחוברים או קשורים זה לזה בשלב מסוים. לפני נקודת ההצטרפות, לרשימות המקושרות יש צמתים שונים וגם אחרי צומת ההצטרפות. הם מיוצגים על ידי רשימה אחת. אז הבעיה היא איך אנו מוצאים צומת (או נקודה) כאלה? יתכן שיש הרבה תשובות / פתרונות אפשריים לבעיה. אך הדרך הפשוטה ביותר היא למצוא את אורכות הרשימות המקושרות. בכל פעם שפתרון הוא פשוט, הוא אינו יעיל מספיק כדי להעביר את מגבלת הזמן. אבל זה לא המקרה כאן. פיתרון זה יעיל ופשוט.

הסבר

בפתרון זה אנו הולכים למצוא את אורכן של שתי הרשימות המקושרות. ואז נעביר את ראש הרשימה המקושרת הארוכה יותר לפני (lenA - lenB) צמתים. פה lenA ו lenB ציין את אורך הרשימה המקושרת A ו- B בהתאמה. אבל למה עשינו את זה?

שקול את אורך הרשימה המקושרת הנפוצה הוא z, אורך הרשימה הארוכה יותר x + z וזה של הרשימה המקושרת הקצרה יותר y + z. אז עד עכשיו עברנו דירה lenA - lenB ברשימה המקושרת הארוכה יותר. זה (x + z - (y + z)) = x - y. פירוש הדבר שעברנו על הרשימה המקושרת הארוכה יותר עד שלצומת בו אנו נמצאים כרגע אורך y מצומת ההצטרפות כמו של ראש הרשימה המקושרת הקצרה יותר. ואז אנחנו עוברים בו זמנית בשתי הרשימות המקושרות ובודקים אם שני הצמתים הנוכחיים שווים. אם כן, מצאנו את נקודת הצומת שלנו. אבל אם לא נמצא נקודה כזו עד סוף הרשימות המקושרות. ואז זה מצביע על כך שאין להם נקודת צומת.

אז ככה אנחנו כותבים פונקציה כדי להשיג את נקודת החיתוך של שתי רשימות מקושרות.

קופונים

קוד C ++ לאיתור צומת שתי רשימות מקושרות

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
  int data;
  ListNode *next;
};

ListNode* create(int data){
  ListNode* tmp = new ListNode();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

int length(ListNode *tmp){
    int cnt =  0;
    while(tmp != NULL){
        cnt++;
        tmp = tmp->next;
    }
    return cnt;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = length(headA);
    int lenB = length(headB);
    
    if(lenA > lenB){
        int cnt = lenA - lenB;
        while(cnt--)
            headA = headA->next;
    } else {
        int cnt = lenB - lenA;
        while(cnt--)
            headB = headB->next;
    }
    while(headA != NULL && headB != NULL){
        if(headA == headB)
            return headA;
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}

int main(){
  ListNode *headA = create(1);
  headA->next = create(2);
  ListNode *headB = create(3);
  headB->next = create(4);
  headA->next->next = headB->next->next = create(5);
  headA->next->next->next = headB->next->next->next = create(6);

  cout<<"Intersection at node: ";
  cout<<getIntersectionNode(headA, headB)->data<<endl;
}
Intersection at node: 5

קוד Java למציאת צומת שתי רשימות מקושרות

import java.util.*;
class ListNode{
  int data;
  ListNode next;
}

class Main{

    static ListNode create(int data){
        ListNode tmp = new ListNode();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

    static int length(ListNode tmp){
        int cnt =  0;
        while(tmp != null){
            cnt++;
            tmp = tmp.next;
        }
        return cnt;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA);
        int lenB = length(headB);

        if(lenA > lenB){
            int cnt = lenA - lenB;
            while(cnt-- > 0)
                headA = headA.next;
        } else {
            int cnt = lenB - lenA;
            while(cnt-- > 0)
                headB = headB.next;
        }
        while(headA != null && headB != null){
            if(headA == headB)
                return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;        
    }

    public static void main(String[] args){
    	ListNode headA = create(1);
    headA.next = create(2);
    ListNode headB = create(3);
    headB.next = create(4);
    headA.next.next = headB.next.next = create(5);
    headA.next.next.next = headB.next.next.next = create(6);

    System.out.print("Intersection at node: ");
    System.out.print(getIntersectionNode(headA, headB).data);
  }
}
Intersection at node: 5

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

מורכבות זמן

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

מורכבות בחלל

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