# 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.

## Comments

## Post a Comment