Intersection of two linked lists

ghz 10months ago ⋅ 67 views

To find the intersection point of two linked lists, you can use the following approach:

  1. Find the lengths of both linked lists.
  2. Calculate the difference in lengths between the two lists.
  3. Traverse the longer list by the difference in lengths.
  4. Traverse both lists in parallel until you find a common node or reach the end of one of the lists.

Here's a Java implementation:

public class IntersectionLinkedList {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        // Find the lengths of both lists
        int lenA = getLength(headA);
        int lenB = getLength(headB);

        // Calculate the difference in lengths
        int diff = Math.abs(lenA - lenB);

        // Traverse the longer list by the difference in lengths
        ListNode longer = lenA > lenB ? headA : headB;
        ListNode shorter = lenA > lenB ? headB : headA;

        while (diff > 0) {
            longer = longer.next;
            diff--;
        }

        // Traverse both lists in parallel until intersection or end of list
        while (longer != null && shorter != null) {
            if (longer == shorter) {
                return longer; // Intersection found
            }
            longer = longer.next;
            shorter = shorter.next;
        }

        return null; // No intersection found
    }

    private static int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    public static void main(String[] args) {
        // Example usage:
        ListNode common = new ListNode(8);
        common.next = new ListNode(4);
        common.next.next = new ListNode(5);

        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        headA.next.next = common;

        ListNode headB = new ListNode(5);
        headB.next = new ListNode(6);
        headB.next.next = new ListNode(1);
        headB.next.next.next = common;

        ListNode intersection = getIntersectionNode(headA, headB);
        if (intersection != null) {
            System.out.println("Intersection node value: " + intersection.val); // Output: 8
        } else {
            System.out.println("No intersection found.");
        }
    }
}

In this implementation:

  • We define a nested class ListNode to represent a node in the linked list.
  • The getIntersectionNode method finds the intersection node of two linked lists.
  • We first find the lengths of both lists and calculate the difference in lengths.
  • We traverse the longer list by the difference in lengths.
  • Then, we traverse both lists in parallel until we find a common node or reach the end of one of the lists.
  • The getLength method calculates the length of a linked list.
  • In the main method, we test the implementation with two example linked lists and print the value of the intersection node if found.
#algorithm