How to find intersection of two singly linked lists in a simple and optimal way in java

To find the intersection of two singly linked lists in a simple and optimal way, you can use the following approach. The key idea is to align the ends of both linked lists by adjusting the start point of the longer list, and then traverse both lists simultaneously to find the intersection point.

Steps:

Calculate Lengths: First, calculate the lengths of both linked lists.
Align Start Pointers: If one list is longer than the other, advance its pointer to align the lengths of both lists.
Find Intersection: Traverse both lists simultaneously. The first node where they meet is the intersection point.

Java Implementation:

class ListNode {
    int val;
    ListNode next;

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

public class LinkedList {

    // Function to get the intersection node of two linked lists
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        // Calculate the lengths of both linked lists
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);

        // Align the start of both lists
        while (lengthA > lengthB) {
            headA = headA.next;
            lengthA--;
        }

        while (lengthB > lengthA) {
            headB = headB.next;
            lengthB--;
        }

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

        return headA;  // or headB, they are the same at intersection point
    }

    // Utility function to calculate the length of a linked list
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    // Function to print the linked list
    public void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Create two linked lists
        // List A: 1 -> 3 -> 5 -> 7 -> 9 -> 11
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(3);
        headA.next.next = new ListNode(5);
        headA.next.next.next = new ListNode(7);
        headA.next.next.next.next = new ListNode(9);
        headA.next.next.next.next.next = new ListNode(11);

        // List B: 2 -> 4 -> 9 -> 11
        ListNode headB = new ListNode(2);
        headB.next = new ListNode(4);
        headB.next.next = headA.next.next.next.next;  // 9
        headB.next.next.next = headA.next.next.next.next.next;  // 11

        System.out.println("List A:");
        list.printList(headA);

        System.out.println("List B:");
        list.printList(headB);

        // Find intersection
        ListNode intersection = list.getIntersectionNode(headA, headB);

        if (intersection != null) {
            System.out.println("Intersection at node with value: " + intersection.val);
        } else {
            System.out.println("No intersection.");
        }
    }
}

Explanation:

ListNode Class:
- Represents each node in the linked list with a value (val) and a pointer to the next node (next).
getIntersectionNode Method:
- Calculate Lengths: The lengths of both linked lists are calculated using the getLength method.
- Align Start Pointers: If the lists have different lengths, the longer list's pointer is advanced to align with the shorter list's pointer.
- Traverse Together: Both pointers are then moved simultaneously. The first node where they match is the intersection node.
getLength Method:
- A helper method to calculate the length of a linked list.
printList Method:
- A utility function to print the nodes of the linked list.
main Method:
- Create two linked lists: For example, 1 -> 3 -> 5 -> 7 -> 9 -> 11 and 2 -> 4 -> 9 -> 11, where the intersection starts at node 9.
- Find and print the intersection: The program will output 9 as the intersection point.

Complexity:

Time Complexity: ( O(m + n) ), where ( m ) and ( n ) are the lengths of the two linked lists. The lists are traversed a maximum of twice.
Space Complexity: ( O(1) ), since only a few extra pointers are used.

This method is simple and optimal, ensuring that you find the intersection point of two singly linked lists in an efficient manner.

Blog

How to find intersection of two singly linked lists in a simple and optimal way in java

Shivam Tyagi

Steps:

Java Implementation:

Explanation:

Complexity:

Join Our Newsletter. No Spam, Only the good stuff.

Related