Напішыце функцыю, каб атрымаць кропку перасячэння двух звязаных спісаў


Узровень складанасці Лёгка
Часта пытаюцца ў Акаліта амазонка DE Шоу Факты Goldman Sachs MakeMyTrip MAQ Microsoft Qualcomm 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)) = х - у. Гэта азначае, што мы перайшлі да больш звязанага спісу, пакуль вузел, на якім мы знаходзімся, таксама не мае даўжыні 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), адзінае, што мы захавалі, гэта даўжыня звязаных спісаў, што робіць гэты алгарытм толькі пастаяннай прасторай.