Intersection of Two Linked Lists - Python Solution

1. Introduction

The "Intersection of Two Linked Lists" problem is a fascinating challenge that involves finding the node where two singly linked lists intersect. This problem tests one's ability to manipulate and traverse linked lists efficiently. It is a common question in interviews to assess understanding of linked list operations and pointer manipulation.

Problem

Given the heads of two singly linked lists headA and headB, the task is to return the node at which the two lists intersect. If the two linked lists have no intersection, return null.

2. Solution Steps

1. Initialize two pointers, pA and pB, pointing to the heads of headA and headB, respectively.

2. Traverse the lists with these pointers.

3. When pA reaches the end of list headA, redirect it to the head of headB. Similarly, when pB reaches the end of headB, redirect it to headA.

4. If the lists intersect, pA and pB will eventually meet at the intersection node.

5. If the lists do not intersect, pA and pB will both reach the end (null) simultaneously.

6. Return the node where pA and pB meet, or null if there is no intersection.

3. Code Program

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def getIntersectionNode(headA, headB):
    pA, pB = headA, headB

    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA

    return pA

# Example Usage
# Creating two intersecting lists for demonstration
# List A: 1 -> 9 -> 1 -> 2 -> 4
# List B: 3 -------> 2 -> 4 (intersect at node with value 2)
common = ListNode(2, ListNode(4))
listA = ListNode(1, ListNode(9, ListNode(1, common)))
listB = ListNode(3, common)
print(getIntersectionNode(listA, listB).val)  # Output: 2

# Lists with no intersection
listA = ListNode(1, ListNode(2))
listB = ListNode(3)
print(getIntersectionNode(listA, listB))  # Output: None

Output:

2
None

Explanation:

1. ListNode Class: ListNode class is used to represent each node in the linked lists.

2. Pointer Initialization: Two pointers pA and pB are used to traverse headA and headB.

3. Traversal Logic: Each pointer traverses its respective list and then the other list.

4. Intersection Detection: If the lists intersect, pA and pB will meet at the intersection node.

5. No Intersection Handling: If there is no intersection, pA and pB will both reach null.

6. Efficient Approach: This method efficiently detects the intersection without extra space or modifying the lists.

7. Result: The function returns the intersecting node or null if there is no intersection.