เขียนฟังก์ชันเพื่อหาจุดตัดของรายการที่เชื่อมโยงสองรายการ


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคโคไลท์ อเมซอน เดอชอว์ ข้อเท็จจริง แซคส์โกลด์แมน MakeMyTrip MAQ ไมโครซอฟท์ วอลคอมม์ Snapdeal วีซ่า ซอปเปอร์
รายการที่เชื่อมโยง

คำชี้แจงปัญหา

ปัญหา“ เขียนฟังก์ชันเพื่อหาจุดตัดของรายการที่เชื่อมโยงสองรายการ” ระบุว่าคุณได้รับสองรายการที่เชื่อมโยงกัน แต่ไม่ใช่รายการที่เชื่อมโยงกันอย่างอิสระ มีการเชื่อมต่อในบางจุด ตอนนี้คุณต้องหาจุดตัดของสองรายการนี้

ตัวอย่าง

เขียนฟังก์ชันเพื่อหาจุดตัดของรายการที่เชื่อมโยงสองรายการ

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

คำอธิบาย: มีรายการเชื่อมโยงสองรายการที่แสดงในอินพุตซึ่ง ได้แก่ 1, 2, 5, 6 และ 3, 4, 5, 6 ทั้งสองรายการถูกรวมเข้าด้วยกันที่โหนดซึ่งมีค่าเป็น 5 ดังนั้นเอาต์พุตจึงเป็น 5

เข้าใกล้

ปัญหาเป็นเรื่องง่ายที่จะอธิบาย มีสอง รายการที่เชื่อมโยง แต่มีการเชื่อมต่อหรือเชื่อมต่อกันในบางจุด ก่อนจุดเข้าร่วมรายการที่เชื่อมโยงทั้งสองมีโหนดต่างกันและตามหลังโหนดการเข้าร่วม พวกเขาแสดงโดยรายการเดียว ดังนั้นปัญหาคือเราจะหาโหนด (หรือจุด) ดังกล่าวได้อย่างไร? อาจมีคำตอบ / วิธีแก้ปัญหาที่เป็นไปได้หลายประการ แต่วิธีที่ง่ายที่สุดคือค้นหาความยาวของรายการที่เชื่อมโยง เมื่อใดก็ตามที่วิธีแก้ปัญหานั้นง่าย แต่ก็ไม่มีประสิทธิภาพเพียงพอที่จะผ่านเวลาที่กำหนด แต่นั่นไม่ใช่กรณีที่นี่ โซลูชันนี้มีประสิทธิภาพและเรียบง่าย

คำอธิบาย

ในวิธีนี้เราจะหาความยาวของรายการที่เชื่อมโยงกันสองรายการ จากนั้นเราจะย้ายส่วนหัวของรายการที่เชื่อมโยงอีกต่อไปข้างหน้าโดย (เลน - lenB) โหนด ที่นี่ เลน และ lenB แสดงความยาวของรายการที่เชื่อมโยง A และ B ตามลำดับ แต่ทำไมเราถึงทำเช่นนี้?

พิจารณาความยาวของรายการที่เชื่อมโยงทั่วไปคือ z ความยาวของรายการที่ยาวกว่าคือ x + z และรายการเชื่อมโยงที่สั้นกว่าคือ y + z. จนถึงตอนนี้เราได้ย้าย lenA - lenB ในรายการที่เชื่อมโยงอีกต่อไป นั่นคือ (x + z - (y + z)) = x - ย. ซึ่งหมายความว่าเราได้ย้ายไปยังรายการที่เชื่อมโยงอีกต่อไปจนกระทั่งโหนดที่เรายืนอยู่นั้นมีความยาวเช่นกัน 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 (1), สิ่งเดียวที่เราเก็บไว้คือความยาวของรายการที่เชื่อมโยงซึ่งทำให้อัลกอริทึมนี้ใช้พื้นที่คงที่เท่านั้น