# Intersection of Two Linked Lists
**Difficulty:** EASY
[External](https://leetcode.com/problems/intersection-of-two-linked-lists)
Canonical: https://scaleengineer.com/dsa/problems/intersection-of-two-linked-lists
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Hash Table, Linked List
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Airbnb](https://scaleengineer.com/companies/airbnb), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [TikTok](https://scaleengineer.com/companies/tiktok), [VMware](https://scaleengineer.com/companies/vmware)
---
## Problem
Given the heads of two singly linked-lists `headA` and `headB`, return _the node at which the two lists intersect_. If the two linked lists have no intersection at all, return `null`.

For example, the following two linked lists begin to intersect at node `c1`:

![](https://assets.glich.co/dsa/intersection-of-two-linked-lists/image0.png) 

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

**Note** that the linked lists must **retain their original structure** after the function returns.

**Custom Judge:**

The inputs to the **judge** are given as follows (your program is **not** given these inputs):

* `intersectVal` \- The value of the node where the intersection occurs. This is `0` if there is no intersected node.
* `listA` \- The first linked list.
* `listB` \- The second linked list.
* `skipA` \- The number of nodes to skip ahead in `listA` (starting from the head) to get to the intersected node.
* `skipB` \- The number of nodes to skip ahead in `listB` (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, `headA` and `headB` to your program. If you correctly return the intersected node, then your solution will be **accepted**.

**Example 1:**

![](https://assets.glich.co/dsa/intersection-of-two-linked-lists/image1.png) 

**Input:** intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
**Output:** Intersected at '8'
**Explanation:** The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

**Example 2:**

![](https://assets.glich.co/dsa/intersection-of-two-linked-lists/image2.png) 

**Input:** intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
**Output:** Intersected at '2'
**Explanation:** The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

**Example 3:**

![](https://assets.glich.co/dsa/intersection-of-two-linked-lists/image3.png) 

**Input:** intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
**Output:** No intersection
**Explanation:** From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

**Constraints:**

* The number of nodes of `listA` is in the `m`.
* The number of nodes of `listB` is in the `n`.
* `1 <= m, n <= 3 * 104`
* `1 <= Node.val <= 105`
* `0 <= skipA <= m`
* `0 <= skipB <= n`
* `intersectVal` is `0` if `listA` and `listB` do not intersect.
* `intersectVal == listA[skipA] == listB[skipB]` if `listA` and `listB` intersect.

**Follow up:** Could you write a solution that runs in `O(m + n)` time and use only `O(1)` memory?

# Approaches
## Brute Force using Nested Loops
The most straightforward approach is to iterate through every node in the first list (`listA`) and, for each node, iterate through every node in the second list (`listB`) to check if they are the same node (i.e., have the same memory reference).
**Time:** O(m * n) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** Highly inefficient, leading to a 'Time Limit Exceeded' error on large inputs.
### Explanation
This method systematically checks every possible pair of nodes from the two lists. For each node in `listA`, it traverses the entire `listB` to look for a reference match. While simple, its performance degrades quadratically with the size of the lists, making it impractical for large inputs.

```java
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ptrA = headA;
        while (ptrA != null) {
            ListNode ptrB = headB;
            while (ptrB != null) {
                if (ptrA == ptrB) {
                    return ptrA;
                }
                ptrB = ptrB.next;
            }
            ptrA = ptrA.next;
        }
        return null;
    }
}
```
### Algorithm
*   Initialize a pointer `ptrA` to `headA`.
*   Loop through `listA` with `ptrA`.
*   Inside this loop, start another pointer `ptrB` at `headB`.
*   Loop through `listB` with `ptrB`.
*   In the inner loop, compare the pointers by reference: `if (ptrA == ptrB)`.
*   If they are the same, we have found the intersection node. Return `ptrA`.
*   If the loops complete without finding a match, the lists do not intersect. Return `null`.

## Hash Set
A more efficient approach is to use a hash set to trade space for time. We can store all the nodes of one list in a hash set. Then, we iterate through the second list and for each node, we check if it's already in the hash set. The first node we find that is already in the set is our intersection point.
**Time:** O(m + n) · **Space:** O(m)
**Pros:** Significantly faster than the brute-force approach with linear time complexity.
**Cons:** Requires extra space proportional to the length of one of the lists.
### Explanation
By using a hash set, we can check for the existence of a node in O(1) average time. We first traverse one list (say, `listA`) and store each node's reference in the set. This takes O(m) time. Then, we traverse the second list (`listB`), and for each node, we check if it's in our set. The first match we find is the intersection. This second traversal takes O(n) time. The overall time complexity is therefore linear, at the cost of using extra space for the hash set.

```java
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> nodesInA = new HashSet<>();
        ListNode ptrA = headA;
        while (ptrA != null) {
            nodesInA.add(ptrA);
            ptrA = ptrA.next;
        }

        ListNode ptrB = headB;
        while (ptrB != null) {
            if (nodesInA.contains(ptrB)) {
                return ptrB;
            }
            ptrB = ptrB.next;
        }

        return null;
    }
}
```
### Algorithm
*   Create a `HashSet<ListNode>`.
*   Iterate through the first list (`listA`) with a pointer `ptrA`.
*   For each node visited, add its reference to the hash set.
*   After populating the set, iterate through the second list (`listB`) with a pointer `ptrB`.
*   For each node visited, check if its reference exists in the hash set.
*   If `set.contains(ptrB)` is true, then `ptrB` is the intersection node. Return `ptrB`.
*   If the second list is fully traversed without finding a match, there is no intersection. Return `null`.

## Two Pointers
The most optimal solution uses two pointers and runs in linear time with constant space. The core idea is to have two pointers traverse the lists in a way that they travel the same total distance. If they meet, they meet at the intersection. If the lists don't intersect, they will both reach the end (`null`) at the same time.
**Time:** O(m + n) · **Space:** O(1)
**Pros:** Optimal solution with linear time and constant space complexity.; Elegant and concise implementation.; Satisfies the follow-up requirement.
**Cons:** The logic of why the pointers meet can be slightly non-obvious at first.
### Explanation
This approach cleverly eliminates the need to calculate the lengths of the lists first. Let's say `listA` has `a` unique nodes and `listB` has `b` unique nodes, and they share `c` common nodes. `ptrA` will travel `a+c` nodes, then switch to `headB` and travel `b` more nodes before reaching the intersection. Total distance: `a+c+b`. `ptrB` will travel `b+c` nodes, then switch to `headA` and travel `a` more nodes to reach the intersection. Total distance: `b+c+a`. Since both pointers travel the same distance at the same speed, they are guaranteed to meet at the intersection point. If there is no intersection (`c=0`), `ptrA` travels `a+b` and `ptrB` travels `b+a`. They will both become `null` at the same time after traversing both lists, correctly returning `null`.

```java
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode ptrA = headA;
        ListNode ptrB = headB;

        while (ptrA != ptrB) {
            ptrA = (ptrA == null) ? headB : ptrA.next;
            ptrB = (ptrB == null) ? headA : ptrB.next;
        }

        return ptrA;
    }
}
```
### Algorithm
*   Initialize two pointers: `ptrA = headA` and `ptrB = headB`.
*   Loop as long as `ptrA` is not equal to `ptrB`.
*   Inside the loop, advance both pointers by one step.
*   A key trick is used: if a pointer reaches the end of its list (`null`), it is redirected to the head of the *other* list. So, if `ptrA` becomes `null`, we set `ptrA = headB`. If `ptrB` becomes `null`, we set `ptrB = headA`.
*   The loop terminates when `ptrA == ptrB`. The value of `ptrA` (or `ptrB`) at this point is the intersection node, or `null` if there is no intersection.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode ( ListNode headA , ListNode headB ) { ListNode a = headA , b = headB ; while ( a != b ) { a = a == null ? headB : a . next ; b = b == null ? headA : b . next ; } return a ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode =
  function (headA, headB) {
    let a = headA;
    let b = headB;
    while (a != b) {
      a = a ? a.next : headB;
      b = b ? b.next : headA;
    }
    return a;
  };

```

### CPP

```cpp
/** * 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 ) { ListNode * a = headA , * b = headB ; while ( a != b ) { a = a ? a -> next : headB ; b = b ? b -> next : headA ; } return a ; } };
```

### Python

```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 : a , b = headA , headB while a != b : a = a . next if a else headB b = b . next if b else headA return a
```