*529*

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`

:

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:**

**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 (2^{nd} node in A and 3^{rd} 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 (3^{rd} node in A and 4^{th} node in B) point to the same location in memory.

# Intuition

The problem states that we need to find the intersection of two linked lists without changing their original structure.

# Approach 1

- Find the length of both the linked lists.
- Traverse the bigger linked list until the remaining nodes count becomes equal to the smaller one’s.
- Traverse both the heads together. If both of them are same then the intersecting node is found.

# Complexity

- Time complexity: O(n) where n>m
- Space complexity: O(1)

```
class Solution {
public:
int length(ListNode *head){
int len = 0;
while(head){
len++;
head = head->next;
}
return len;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA || !headB) return NULL;
//step1
int lenA = length(headA), lenB = length(headB);
//step2
if(lenA>lenB){
while(lenA>lenB){
headA = headA->next;
lenA--;
}
}
else if(lenA<lenB){
while(lenA<lenB){
headB = headB->next;
lenB--;
}
}
//step 3
while(headA && headB){
if(headA==headB) return headA;
headA = headA->next;
headB = headB->next;
}
return NULL;
}
};
```

# Approach 2

Prerequisite : https://leetcode.com/problems/linked-list-cycle-ii/

In this approach, we can simply convert this problem into a loop problem.

- Find the tail.
- Connect the tail with any of the head which creates a loop.
- Using the other head, find intersection point of the loop.
- Undo the loop, by setting
`tail->next = NULL`

- Return the intersection node.

# Complexity

- Time complexity: O(n+m)
- Space complexity: O(1)

```
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//getting the tail
ListNode* tail = headA;
while(tail->next){
tail = tail->next;
}
//creating a loop
tail->next = headA;
//detecting and finding the intersection
ListNode *fast = headB, *slow = headB;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow==fast) {
slow = headB;
while(slow!=fast){
slow = slow->next;
fast = fast->next;
}
//undoing the loop
tail->next = NULL;
return slow;
};
}
tail->next = NULL;
return NULL;
}
```