ค้นหาจุดตัดของสองรายการที่เชื่อมโยงใน Java

รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลเชิงเส้นซึ่งแต่ละโหนดมีสองบล็อก โดยที่หนึ่งบล็อกมีค่าหรือข้อมูลของโหนด และอีกบล็อกหนึ่งมีที่อยู่ของฟิลด์ถัดไป

สมมติว่าเรามีรายการที่เชื่อมโยง โดยที่แต่ละโหนดมีตัวชี้สุ่มซึ่งชี้ไปยังโหนดอื่นในรายการ ภารกิจคือการค้นหาโหนดที่รายการที่เชื่อมโยงสองรายการตัดกัน หากไม่ตัดกัน ให้คืนค่า NULL หรือค่าว่างเป็นเอาต์พุต

ตัวอย่าง

อินพุต-1:

ผลลัพธ์:

2

คำอธิบาย: เนื่องจากรายการเชื่อมโยงที่กำหนดตัดกันที่โหนดด้วยค่า '2' เราจะคืนค่า '2' เป็นผลลัพธ์

อินพุต-2:

ผลลัพธ์:

NULL

คำอธิบาย: เนื่องจากไม่มีจุดร่วม เราจะคืนค่า NULL ในกรณีนี้

แนวทางในการแก้ปัญหานี้

เรามีรายการที่เชื่อมโยงสองรายการที่มีจุดร่วมที่พวกมันตัดกัน ในการหาจุดตัด เราจะสำรวจทั้งสองรายการที่เชื่อมโยงจนพบว่าชี้ไปที่ค่าเดียวกันเท่ากัน ในบางจุด ตัวชี้ไปยังโหนดถัดไปของรายการที่เชื่อมโยงจะเหมือนเดิม ดังนั้นเราจะคืนค่าของจุดนั้น

• นำรายการที่เชื่อมโยงสองรายการพร้อมข้อมูลและตัวชี้ไปยังโหนดถัดไป
• ฟังก์ชัน commonPoint(listnode*headA, listnode*headB) รับตัวชี้สองตัวของรายการที่เชื่อมโยงตามลำดับและส่งกลับค่าของจุดร่วมหรือจุดตัดของรายการที่เชื่อมโยง
• ฟังก์ชันจำนวนเต็มที่ค้นหาความยาวของรายการที่เชื่อมโยงจะคืนค่าความยาวของรายการที่เชื่อมโยงทั้งสองจากส่วนหัวของรายการ
• ตอนนี้สร้างตัวชี้ไปที่ส่วนหัวของทั้งสองรายการและสำรวจรายการซึ่งมีความยาวมากกว่าจนถึง (ความยาวของรายการแรก – ความยาวของรายการที่สอง)
• ตอนนี้สำรวจรายการจนกว่าเราจะพบว่าตัวชี้ถัดไปเท่ากัน
• คืนค่าของโหนดเฉพาะที่รายการทั้งสองตัดกัน

ตัวอย่าง

public class Solution {
   static listnode headA,
   headB;
   static class listnode {
      int data;
      listnode next;
      listnode(int d) {
         data = d;
         next = null;
      }
   }
   int count(listnode head) {
      int c = 0;
      while (head != null) {
         c++;
         head = head.next;
      }
      return c;
   }
   int commonPoint(listnode headA, listnode headB) {
      listnode p1 = headA;
      listnode p2 = headB;
      int c1 = count(headA);
      int c2 = count(headB);
      if (c1 > c2) {
         for (int i = 0; i < c1 - c2; i++) {
            if (p1 == null) {
               return - 1;
            }
            p1 = p1.next;
         }
      }
      if (c1 < c2) {
         for (int i = 0; i < c2 - c1; i++) {
            if (p2 == null) {
               return - 1;
            }
            p2 = p2.next;
         }
      }
      while (p1 != null &amp;&amp; p2 != null) {
         if (p1.data == p2.data) {
            return p1.data;
         }
         p1 = p1.next;
         p2 = p2.next;
      }
      return - 1;
   }
   public static void main(String[] args) {
      Solution list = new Solution();
      list.headA = new listnode(5);
      list.headA.next = new listnode(4);
      list.headA.next.next = new listnode(9);
      list.headA.next.next.next = new listnode(7);
      list.headA.next.next.next.next = new listnode(1);
      list.headB = new listnode(6);
      list.headB.next = new listnode(7);
      list.headB.next.next = new listnode(1);
      System.out.println(list.commonPoint(headA, headB));
   }
}

การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น

ผลลัพธ์

7

คำอธิบาย :รายการเชื่อมโยงที่กำหนดจะตัดกันที่ 7