Table of contents

Intersection node point of two singly linked lists

Given two singly linked lists that may or may not intersect, find the node at which the two lists intersect. If the two linked lists have no intersection, return None or a special indicator.

Input-Output Examples

Example 1:

  • Input:
    • List1: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
    • List2: 9 -> 8 -> 7 -> 5 -> 6 -> NULL
  • Output: Node with value 5 (The lists intersect at node with value 5)

Example 2:

  • Input:
    • List1: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    • List2: 9 -> 8 -> 7 -> NULL
  • Output: NULL (The lists do not intersect)

Example 3:

  • Input:
    • List1: 1 -> 2 -> 3 -> NULL
    • List2: 3 -> NULL
  • Output: Node with value 3 (The lists intersect at node with value 3)

Approach:
Technique to be used: Two-pointer technique with length adjustment

To find the intersection point of two linked lists, we need to account for the difference in lengths of the two lists. By adjusting the starting point of the longer list, we can ensure that the two pointers meet at the intersection point if there is one.

Steps to implement:

  1. Calculate the lengths of both linked lists.
  2. Find the difference in lengths (d) and adjust the starting point of the longer list by d nodes.
  3. Traverse both lists simultaneously until the pointers meet at the intersection point or reach the end of the lists.

C++ Program to find the intersection node of two linked lists

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (!headA || !headB) return NULL;
        
        ListNode* a = headA;
        ListNode* b = headB;
        
        // If a & b have different lengths, then we will stop the loop after second iteration
        while (a != b) {
            // for the end of first iteration, we just reset the pointer to the head of another linked list
            a = a ? a->next : headB;
            b = b ? b->next : headA;
        }
        
        return a;
    }
};

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating linked lists
    ListNode* intersect = new ListNode(5);
    intersect->next = new ListNode(6);
    
    ListNode* headA = new ListNode(1);
    headA->next = new ListNode(2);
    headA->next->next = new ListNode(3);
    headA->next->next->next = new ListNode(4);
    headA->next->next->next->next = intersect;

    ListNode* headB = new ListNode(9);
    headB->next = new ListNode(8);
    headB->next->next = new ListNode(7);
    headB->next->next->next = intersect;

    Solution sol;
    ListNode* intersection = sol.getIntersectionNode(headA, headB);

    // Printing the intersection point
    if (intersection) {
        cout << "The intersection node is: " << intersection->val << endl;
    } else {
        cout << "The lists do not intersect." << endl;
    }

    return 0;
}

Java Program to find the intersection node of two linked lists

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        
        ListNode a = headA;
        ListNode b = headB;
        
        // If a & b have different lengths, then we will stop the loop after second iteration
        while (a != b) {
            // for the end of first iteration, we just reset the pointer to the head of another linked list
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        
        return a;
    }
    
    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating linked lists
        ListNode intersect = new ListNode(5);
        intersect.next = new ListNode(6);
        
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);
        headA.next.next.next = new ListNode(4);
        headA.next.next.next.next = intersect;

        ListNode headB = new ListNode(9);
        headB.next = new ListNode(8);
        headB.next.next = new ListNode(7);
        headB.next.next.next = intersect;

        Solution sol = new Solution();
        ListNode intersection = sol.getIntersectionNode(headA, headB);

        // Printing the intersection point
        if (intersection != null) {
            System.out.println("The intersection node is: " + intersection.val);
        } else {
            System.out.println("The lists do not intersect.");
        }
    }
}

Python Program to find the intersection node of two linked lists

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        
        a, b = headA, headB
        
        # If a & b have different lengths, then we will stop the loop after second iteration
        while a != b:
            # for the end of first iteration, we just reset the pointer to the head of another linked list
            a = a.next if a else headB
            b = b.next if b else headA
        
        return a

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating linked lists
intersect = ListNode(5)
intersect.next = ListNode(6)

headA = ListNode(1)
headA.next = ListNode(2)
headA.next.next = ListNode(3)
headA.next.next.next = ListNode(4)
headA.next.next.next.next = intersect

headB = ListNode(9)
headB.next = ListNode(8)
headB.next.next = ListNode(7)
headB.next.next.next = intersect

sol = Solution()
intersection = sol.getIntersectionNode(headA, headB)

# Printing the intersection point
if intersection:
    print("The intersection node is:", intersection.val)
else:
    print("The lists do not intersect.")

Finding the intersection point of two linked lists can be efficiently achieved using the two-pointer technique, which involves adjusting the pointers of each list to traverse both lists. This ensures that the pointers will meet at the intersection point if there is one, with a time complexity of O(n + m), where n and m are the lengths of the two lists.

DSA

Related Articles