Find Intersection Point of Two Linked Lists – Java Program

This Java program demonstrates how to find the intersection point of two linked lists. The program includes the implementation of the linked list nodes and the logic to find the intersection point.

Program Structure

The program is structured into three main components:

1. ListNode Class: Defines the node structure for the linked list.
2. FindIntersection Class: Contains the method to find the intersection point of two linked lists.
3. Main Class: Contains the main method to execute the program and test the intersection functionality.

Java Code

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public class FindIntersection {
        /**
         * Finds the intersection point of two linked lists.
         * 
         * @param headA The head of the first linked list.
         * @param headB The head of the second linked list.
         * @return The intersection point node or null if no intersection.
         */
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            
            ListNode pointerA = headA;
            ListNode pointerB = headB;
            
            // Traverse both lists
            while (pointerA != pointerB) {
                // When reaching the end of a list, redirect to the start of the other list
                pointerA = (pointerA == null) ? headB : pointerA.next;
                pointerB = (pointerB == null) ? headA : pointerB.next;
            }
            
            // Either both pointers meet at the intersection node or both are null
            return pointerA;
        }
    }

    public class Main {
        public static void main(String[] args) {
            // Create two linked lists with an intersection for testing
            ListNode common = new ListNode(8, new ListNode(10));
            ListNode headA = new ListNode(3, new ListNode(7, common));
            ListNode headB = new ListNode(99, new ListNode(1, common));
            
            // Find the intersection point
            FindIntersection finder = new FindIntersection();
            ListNode intersection = finder.getIntersectionNode(headA, headB);
            
            // Print the intersection point
            if (intersection != null) {
                System.out.println("The intersection point has value: " + intersection.val);
            } else {
                System.out.println("No intersection point.");
            }
        }
    }
    

Explanation

ListNode Class: This class represents a node in the linked list. Each node contains an integer value and a reference to the next node.

FindIntersection Class: This class contains the method getIntersectionNode that finds the intersection point of two linked lists. It uses the two-pointer technique to efficiently find the intersection.

Main Class: This class is used for testing the intersection functionality. It creates two sample linked lists with an intersection, finds the intersection point using the FindIntersection class, and prints the result.