Intersection of Two Linked Lists - Java Solution

1. Introduction

In this post, we will explore a solution to the "Intersection of Two Linked Lists" problem. This problem involves finding a node where two singly linked lists intersect. Understanding linked list traversal and pointer manipulation is key to solving this challenge effectively.

Problem

The goal is to find the node at which two singly linked lists, headA and headB, intersect. If there is no intersection, the function should return null.

2. Solution Steps

1. Calculate the lengths of both linked lists.

2. Adjust the starting point of the longer list so that both lists have an equal number of nodes to traverse until the end.

3. Traverse both lists simultaneously until a common node is found or the end of the lists is reached.

4. If a common node is found, return it; otherwise, return null.

3. Code Program

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class IntersectionOfTwoLinkedLists {
    public static void main(String[] args) {
        // Example use case
        // List A
        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        ListNode intersect = new ListNode(8);
        headA.next.next = intersect;
        intersect.next = new ListNode(4);
        intersect.next.next = new ListNode(5);

        // List B
        ListNode headB = new ListNode(5);
        headB.next = new ListNode(6);
        headB.next.next = new ListNode(1);
        headB.next.next.next = intersect;

        ListNode result = getIntersectionNode(headA, headB);
        System.out.println(result != null ? result.val : "null");
    }

    // Function to get the intersection node of two linked lists
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA);
        int lenB = length(headB);

        // Align both lists at the same start point
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        while (lenB > lenA) {
            headB = headB.next;
            lenB--;
        }

        // Traverse the lists to find the intersection
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }

        return headA;
    }

    // Helper method to calculate the length of a linked list
    private static int length(ListNode node) {
        int length = 0;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }
}

Output:

8

Explanation:

1. getIntersectionNode: This function finds the intersection node of two singly linked lists.

2. It starts by calculating the lengths of both lists using the length helper method.

3. The lists are then aligned to start at the same point from the end by advancing the head of the longer list.

4. The function then simultaneously traverses both lists until it finds a common node or reaches the end.

5. If a common node is found (i.e., headA == headB), it is returned as the intersection; otherwise, the function returns null.

6. This method efficiently finds the intersection point without using additional memory for data structures like hash maps.