Java Program to Find Intersection Point in Y Shaped Linked List in Java

2025年5月6日 | 阅读 9 分钟

Y 形链表是一种链表，其中两条不同的链表在一个共享的交点处相遇。在这个 Java 程序中，我们演示了如何确定两条链表汇合的交点。该方法包括遍历两条链表以验证它们是否有任何共同节点，并提供第一个共享节点作为交点。

使用暴力方法

确定两个链表交点的暴力方法包括将第一个链表的每个节点与第二个链表的每个节点进行比较。它检查每一对可能的节点，直到出现交点，或者在没有找到匹配项的情况下完全遍历两个链表。

算法

步骤 1：将 ptr1 设置为第一个链表的头，将 ptr2 设置为第二个链表的头。

步骤 2：逐个节点移动 ptr1，遍历第一个链表。

步骤 3：对于第一个链表中的每个节点，遍历第二个链表以比较节点。

步骤 4：如果 ptr1 和 ptr2 指向同一个节点，那就是交点。返回该节点。

步骤 5：如果检查完所有节点但未找到匹配项，则返回 null，表示没有交点。

实施

文件名：LinkedListIntersectionBruteForce.java

import java.io.*;
// Node class for linked list
class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        next = null;
    }
}
public class LinkedListIntersectionBruteForce {
    // Method to find the intersection point using the brute-force approach
    public static Node getIntersectionPoint(Node head1, Node head2) {
        Node ptr1 = head1; // Pointer to traverse the first list
        while (ptr1 != null) {
            Node ptr2 = head2; // Pointer to traverse the second list
            while (ptr2 != null) {
                if (ptr1 == ptr2) { // Intersection point found
                    return ptr1;
                }
                ptr2 = ptr2.next;
            }
            ptr1 = ptr1.next;
        }
        return null; // No intersection
    }
    public static void main(String[] args) {
        // Create linked lists
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        Node intersection = new Node(4);
        head1.next.next.next = intersection;
        intersection.next = new Node(5);
        Node head2 = new Node(6);
        head2.next = intersection; // Create the Y-shape by pointing to the same node
        // Find intersection point
        Node result = getIntersectionPoint(head1, head2);
        if (result != null) {
            System.out.println("Intersection point data: " + result.data);
        } else {
            System.out.println("No intersection point found.");
        }
    }
}   

输出

 
Intersection point data: 4

时间复杂度： O(N * M)，其中 N 和 M 是两个链表的长度。这是因为对于第一个链表中的每个节点，我们都将其与第二个链表中的每个节点进行比较。

空间复杂度： O(1)，因为除了指针之外，不使用任何额外的空间。

使用哈希方法

在这种方法中，我们遍历第一个链表并将所有节点存储在 HashSet 中。然后，我们遍历第二个链表，将每个节点与 HashSet 进行比较，以高效地找到交点。

算法

步骤 1：创建一个空的 HashSet 来存储第一个链表的节点。

步骤 2：将第一个链表的所有节点添加到 HashSet 中。

步骤 3：遍历第二个链表，检查是否有任何节点在 HashSet 中。

步骤 4：如果找到交点，则返回该节点；否则，继续检查。

步骤 5：如果没有找到交点，则返回 null。

实施

文件名：LinkedListIntersectionHashing.java

import java.io.*;
import java.util.HashSet;
class Node {
    int data; // Data part of the node
    Node next; // Reference to the next node in the list
    // Constructor to initialize the node with data
    Node(int data) {
        this.data = data; // Assign the provided data to the node
        next = null; // Initially, the next node is null
    }
}
// Main class to find the intersection point of two linked lists
public class LinkedListIntersectionHashing {
    // Method to find the intersection point of two linked lists using hashing
    public static Node getIntersectionPoint(Node head1, Node head2) {
        HashSet<Node> nodes = new HashSet<>();
        // Traverse the first linked list and add all nodes to the hash set
        Node current = head1; // Initialize current pointer to the head of the first list
        while (current != null) { // Loop until the end of the first list
            nodes.add(current); // Add the current node to the hash set
            current = current.next; // Move to the next node
        }
        // Traverse the second linked list to find the intersection point
        current = head2; // Initialize current pointer to the head of the second list
        while (current != null) { // Loop until the end of the second list
            if (nodes.contains(current)) { // Check if the current node exists in the hash set
                return current; // If found, return the intersection point
            }
            current = current.next; // Move to the next node
        }
        return null; // If no intersection point is found, return null
    }
    public static void main(String[] args) {
        Node head1 = new Node(1); 
        head1.next = new Node(2); 
        head1.next.next = new Node(3); 
        Node intersection = new Node(4); // Create the intersection node with data 4
        head1.next.next.next = intersection; // Link the third node to the intersection node
        intersection.next = new Node(5); // Add a new node with data 5 after the intersection
        // Create the second linked list: 6 → 4 → 5
        Node head2 = new Node(6); // Create the head node with data 6
        head2.next = intersection; // Link the head of the second list to the intersection node
        // Find the intersection point of the two linked lists
        Node result = getIntersectionPoint(head1, head2); // Call the method to find the intersection point
        if (result != null) { // Check if an intersection point is found
            System.out.println("Intersection point data: " + result.data); // Print the data of the intersection point
        } else {
            System.out.println("No intersection point found."); // Print a message if there is no intersection
        }
    }
}   

输出

 
Intersection point data: 4

时间复杂度： O(N + M)，其中 N 和 M 分别是第一个和第二个链表的长度。这是因为我们每个链表只遍历一次。

空间复杂度： O(N)，其中 N 是第一个链表中的节点数。这是因为我们使用哈希集来存储来自第一个列表的节点。

使用并行遍历方法

在这种方法中，两个指针同时遍历两个链表。如果它们到达各自链表的末尾，则将它们重定向到另一个链表的头部，确保如果存在交点，它们将在交点处相遇。

算法

步骤 1：将两个指针 ptr1 和 ptr2 初始化为两个链表的头部。

步骤 2：遍历链表

如果指针到达其链表的末尾，则将其重置为相反链表的头部。
如果不是，则将指针移到下一个节点。

步骤 3：继续遍历，直到两个指针相遇。

步骤 4：返回它们相遇的节点作为交点，如果不存在交点则返回 null。

实施

文件名：LinkedListIntersectionParallelTraversal.java

import java.io.*;
class Node {
    int data; // Variable to store the data part of the node
    Node next; // Variable to store the reference to the next node
    // Constructor to initialize a node with the given data
    Node(int data) {
        this.data = data; // Assign the given data to the node
        next = null; // Initialize the next pointer to null
    }
}
// Main class to find the intersection point of two linked lists using parallel traversal
public class LinkedListIntersectionParallelTraversal {
    // Method to find the intersection point of two linked lists
    public static Node getIntersectionPoint(Node head1, Node head2) {
        // Initialize a pointer to traverse the first linked list
        Node ptr1 = head1;
        // Initialize a pointer to traverse the second linked list
        Node ptr2 = head2;
        // Loop until the two pointers either meet at the intersection or both reach null
        while (ptr1 != ptr2) {
            // If ptr1 reaches the end of the first list, move it to the head of the second list
            ptr1 = (ptr1 == null) ? head2 : ptr1.next;
            // If ptr2 reaches the end of the second list, move it to the head of the first list
            ptr2 = (ptr2 == null) ? head1 : ptr2.next;
        }
        // Return the intersection point (either the node or null if there is no intersection)
        return ptr1;
    }
    public static void main(String[] args) {
        Node head1 = new Node(1); 
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        // Create the intersection node with data 4
        Node intersection = new Node(4);
        // Link the third node of the first list to the intersection node
        head1.next.next.next = intersection;
        // Add a node with data 5 after the intersection node
        intersection.next = new Node(5);
        // Create the second linked list: 6 → 4 → 5
        Node head2 = new Node(6); // Create the head node with data 6
        head2.next = intersection; // Link the second list to the intersection node
        // Find the intersection point of the two linked lists
        Node result = getIntersectionPoint(head1, head2);
        // Check if an intersection point was found
        if (result != null) {
            // Print the data of the intersection point
            System.out.println("Intersection point data: " + result.data);
        } else {
            // Print a message if no intersection point was found
            System.out.println("No intersection point found.");
        }
    }
}

输出

 
Intersection point data: 4

时间复杂度： O(N + M)

空间复杂度： O(1)

循环链表方法

此方法利用形成循环链表的概念来检测两个链表中的交点。以下是说明

算法

步骤 1：遍历第一个链表以到达其最后一个节点。

步骤 2：暂时将第一个链表的最后一个节点连接到其头部，形成一个循环链表。

步骤 3：对第二个链表应用 Floyd 的循环检测算法

使用两个指针（慢指针和快指针）来检测循环。
如果没有检测到循环，则返回 null（不存在交点）。

步骤 4：如果存在循环，则识别循环开始的节点（交点）。

步骤 5：通过断开临时连接来恢复第一个链表。

实施

文件名：LinkedListIntersectionCircular.java

import java.io.*;
class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
public class LinkedListIntersectionCircular {
    // Method to find the intersection point using the circular list approach
    public static Node getIntersectionPoint(Node head1, Node head2) {
        // Step 1: Traverse the first list to find its last node
        Node lastNode = head1;
        while (lastNode.next != null) {
            lastNode = lastNode.next;
        }
        // Step 2: Create a circular connection
        lastNode.next = head1;
        // Step 3: Use Floyd's Cycle Detection Algorithm on the second list
        Node intersection = detectCycle(head2);
        // Step 4: Break the circular connection to restore the first list
        lastNode.next = null;
        return intersection;
    }
    // Helper method to detect the starting node of a cycle in a linked list
    private static Node detectCycle(Node head) {
        Node slow = head;
        Node fast = head;
        // Detect if a cycle exists
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) { // Cycle detected
                // Find the starting node of the cycle
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow; // Starting node of the cycle
            }
        }
        return null; // No cycle (no intersection)
    }
    public static void main(String[] args) {
        // Create linked lists
        Node head1 = new Node(1); // First list: 1 → 2 → 3 → 4 → 5
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        Node intersection = new Node(4);
        head1.next.next.next = intersection;
        intersection.next = new Node(5);
        Node head2 = new Node(6); // Second list: 6 → 4 → 5
        head2.next = intersection;
        // Find the intersection point
        Node result = getIntersectionPoint(head1, head2);
        if (result != null) {
            System.out.println("Intersection point data: " + result.data);
        } else {
            System.out.println("No intersection point found.");
        }
    }
}   

输出

 
Intersection point data: 4

时间复杂度：O(N + M)，其中 N 是第一个链表的长度，M 是第二个链表的长度。

辅助空间复杂度：O(1)，因为只使用了常量级别的额外空间。

下一个主题字典序 Java

← 上一个下一个 →

Java Program to Find Intersection Point in Y Shaped Linked List in Java

使用暴力方法

算法

实施

使用哈希方法

算法

实施

使用并行遍历方法

算法

实施

循环链表方法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java Program to Find Intersection Point in Y Shaped Linked List in Java

使用暴力方法

算法

实施

使用哈希方法

算法

实施

使用并行遍历方法

算法

实施

循环链表方法

算法

实施

相关帖子

如何在 Java 中更改日期中的天数

Java 中的 ORM 工具

Float Vs Double Java

Flutter vs Java

Java 中的图像处理 - 改变图像方向

Java 8 BiFunction

Java 中将 String 转换为 Map

Java 中的 java.util.IntSummaryStatistics 类及示例

Java 中的快速排序

如何在 Java 中使字段可序列化

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器