ຂຽນ ໜ້າ ທີ່ເພື່ອຈຸດທີ່ຕັດກັນຂອງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Amazon DE Shaw ປັດໃຈ Goldman Sachs MakeMyTrip MAQ Microsoft Qualcomm Snapdeal ສະແດງໃຫ້ເຫັນ Zopper
ບັນຊີທີ່ເຊື່ອມໂຍງ

ຖະແຫຼງການບັນຫາ  

ບັນຫາ“ ຂຽນຟັງຊັນເພື່ອໃຫ້ຈຸດເຊື່ອມຕໍ່ຂອງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງ” ກ່າວວ່າທ່ານໄດ້ຮັບສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງກັນ. ແຕ່ພວກມັນບໍ່ແມ່ນລາຍການທີ່ເຊື່ອມໂຍງເປັນເອກະລາດ. ພວກເຂົາເຊື່ອມຕໍ່ໃນບາງຈຸດ. ໃນປັດຈຸບັນທ່ານຈໍາເປັນຕ້ອງຊອກຫາຈຸດເຊື່ອມຕໍ່ຂອງສອງລາຍຊື່ນີ້.

ຍົກຕົວຢ່າງ  

ຂຽນ ໜ້າ ທີ່ເພື່ອຈຸດທີ່ຕັດກັນຂອງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງPin

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

ຄຳ ອະທິບາຍ: ມີສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງທີ່ສະແດງຢູ່ໃນວັດສະດຸປ້ອນເຊິ່ງ 1, 2, 5, 6 ແລະ 3, 4, 5, 6. ທັງສອງໄດ້ຖືກລວມເຂົ້າກັນໃນຂໍ້ທີ່ມີຄ່າຂອງມັນ 5. ດັ່ງນັ້ນຜົນໄດ້ຮັບແມ່ນ 5.

ວິທີການ  

ບັນຫາແມ່ນງ່າຍດາຍທີ່ຈະອະທິບາຍ. ມີ​ສອງ ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ ແຕ່ພວກມັນເຂົ້າຮ່ວມຫລືເຊື່ອມໂຍງກັນໃນບາງຈຸດ. ກ່ອນຈຸດເຂົ້າຮ່ວມ, ທັງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງມີຂໍ້ທີ່ແຕກຕ່າງກັນແລະຫຼັງຈາກ node ເຂົ້າຮ່ວມ. ພວກເຂົາຖືກສະແດງໂດຍລາຍຊື່ດຽວ. ດັ່ງນັ້ນ, ບັນຫາແມ່ນວ່າພວກເຮົາຊອກຫາໂຫນດດັ່ງກ່າວ (ຫຼືຈຸດໃດ)? ມັນອາດຈະມີ ຄຳ ຕອບ / ວິທີແກ້ໄຂທີ່ອາດຈະເກີດຂື້ນກັບບັນຫາ. ແຕ່ວິທີທີ່ງ່າຍທີ່ສຸດແມ່ນຊອກຫາຄວາມຍາວຂອງລາຍຊື່ທີ່ເຊື່ອມໂຍງເຂົ້າກັນ. ເມື່ອໃດກໍ່ຕາມວິທີແກ້ໄຂແມ່ນງ່າຍດາຍ, ມັນບໍ່ມີປະສິດທິພາບພຽງພໍທີ່ຈະຜ່ານ ກຳ ນົດເວລາ. ແຕ່ນັ້ນບໍ່ແມ່ນກໍລະນີນີ້. ວິທີແກ້ໄຂນີ້ແມ່ນມີປະສິດທິພາບແລະລຽບງ່າຍ.

ຄໍາອະທິບາຍ

ໃນການແກ້ໄຂບັນຫານີ້, ພວກເຮົາຈະຊອກຫາຄວາມຍາວຂອງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງກັນ. ແລະຫຼັງຈາກນັ້ນພວກເຮົາຈະຍ້າຍຫົວຫນ້າຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ທີ່ຍາວກວ່າຕໍ່ຫນ້າໂດຍ (ເລນ - ເລນບີ) ຂໍ້. ທີ່ນີ້ ເລນ ແລະ ເລນບີ ສະແດງຄວາມຍາວຂອງລາຍຊື່ທີ່ເຊື່ອມໂຍງ A ແລະ B ຕາມ ລຳ ດັບ. ແຕ່ເປັນຫຍັງພວກເຮົາຈຶ່ງເຮັດແບບນີ້?

ເບິ່ງ
ປ່ຽນ ຈຳ ນວນ ໜຶ່ງ ເປັນ Hexadecimal Leetcode Solution

ພິຈາລະນາຄວາມຍາວຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງທົ່ວໄປແມ່ນ z, ຄວາມຍາວຂອງບັນຊີລາຍຊື່ທີ່ຍາວກວ່າແມ່ນ x + z ແລະບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງສັ້ນກວ່ານີ້ແມ່ນ y + z. ສະນັ້ນຈົນເຖິງດຽວນີ້, ພວກເຮົາໄດ້ຍ້າຍໄປແລ້ວ lenA - lenB ໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງກັນຍາວກວ່າ. ນັ້ນ​ແມ່ນ (x + z - (y + z)) = x - y. ນີ້ ໝາຍ ຄວາມວ່າພວກເຮົາໄດ້ຍ້າຍເຂົ້າບັນຊີລາຍຊື່ທີ່ມີການເຊື່ອມໂຍງກັນຍາວກວ່າຈົນກ່ວາ node ທີ່ພວກເຮົາ ກຳ ລັງຢືນຢູ່ນີ້ຍັງມີຄວາມຍາວ y ຈາກ node ເຂົ້າຮ່ວມເປັນຫົວຂໍ້ຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງສັ້ນກວ່າ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາຍ້າຍພ້ອມກັນທັງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງແລະກວດເບິ່ງວ່າທັງສອງ nodes ປັດຈຸບັນແມ່ນເທົ່າທຽມກັນຫລືບໍ່. ຖ້າເປັນດັ່ງນັ້ນ, ພວກເຮົາໄດ້ພົບຈຸດຕັດກັນຂອງພວກເຮົາແລ້ວ. ແຕ່ຖ້າພວກເຮົາບໍ່ພົບຈຸດດັ່ງກ່າວຈົນກວ່າຈະສິ້ນສຸດລາຍຊື່ທີ່ເຊື່ອມໂຍງ. ຫຼັງຈາກນັ້ນນີ້ສະແດງໃຫ້ເຫັນວ່າພວກເຂົາບໍ່ມີຈຸດຕັດກັນ.

ນີ້ແມ່ນວິທີທີ່ພວກເຮົາຂຽນຟັງຊັນເພື່ອໃຫ້ຈຸດຕັດກັນຂອງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງ.

ລະຫັດ  

ລະຫັດ 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

ການວິເຄາະຄວາມສັບສົນ  

ຄວາມສັບສົນເວລາ

ໂອ (N), ນັບຕັ້ງແຕ່ພວກເຮົາໄດ້ແລ່ນຜ່ານແຕ່ລະຂໍ້ຢູ່ໃນລາຍຊື່ທີ່ເຊື່ອມໂຍງກັນຢ່າງແນ່ນອນ. ຖ້າມີຈຸດຕັດກັນແລ້ວເມື່ອພວກເຮົາໄປຮອດຂໍ້ນັ້ນພວກເຮົາສົ່ງມັນຄືນ. ໄປເບິ່ງແຕ່ລະຂໍ້ຂອງຂໍ້ທີ່ຜ່ານໄປ. ນີ້ສະແດງໃຫ້ເຫັນວ່າຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນ.

ເບິ່ງ
ວົງຈອນບັນຊີທີ່ເຊື່ອມໂຍງ

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (1), ສິ່ງດຽວທີ່ພວກເຮົາເກັບໄວ້ແມ່ນຄວາມຍາວຂອງລາຍການທີ່ເຊື່ອມໂຍງເຊິ່ງເຮັດໃຫ້ລະບົບນີ້ໃຊ້ເວລາເທົ່ານັ້ນ.