Last updated on August 5th, 2024 at 01:02 am

Here, We see ** Intersection of Two Linked Lists LeetCode Solution**. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

*List of all LeetCode Solution*

*List of all LeetCode Solution*

## Topics

Linked List

## Companies

Airbnb, Amazon, Bloomberg, Microsoft

## Level of Question

Easy

**Intersection of Two Linked Lists LeetCode Solution**

## Table of Contents

**Problem Statement**

Given the heads of two singly linked-lists ** headA** and

**, return**

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

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

The judge will then create the linked structure based on these inputs and pass the two heads, ** headA **and

**to your program. If you correctly return the intersected node, then your solution will be**

*headB***accepted**.

Example 1:(fig-1)Input:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3Output: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:(fig-2)Input:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1Output: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:(fig-3)Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2Output: No intersectionExplanation: 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.

**1. Intersection of Two Linked Lists Leetcode Solution C++**

class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *ptr1 = headA; ListNode *ptr2 = headB; while(ptr1 != ptr2){ if(ptr1 == NULL){ ptr1 = headB; } else{ ptr1 = ptr1 -> next; } if(ptr2 == NULL){ ptr2 = headA; } else{ ptr2 = ptr2 -> next; } } return ptr1; } };

#### 1.1 Explanation

**Variables:****ptr1**and**ptr2**are initialized to**headA**and**headB**respectively, representing pointers to traverse the two linked lists.**Traversal:**The**while**loop continues until**ptr1**equals**ptr2**, which indicates they have found the intersection node.**Pointer Manipulation:**- If
**ptr1**reaches the end (**NULL**), it continues from**headB**. - If
**ptr2**reaches the end (**NULL**), it continues from**headA**.

- If
**Return:**Once`ptr1`

equals`ptr2`

, they both point to the intersection node, and it is returned.

#### 1.2 Time Complexity

**O(m + n)**, where**m**and**n**are the lengths of**headA**and**headB**respectively.

#### 1.3 Space Complexity

**O(1)**, since only a constant amount of extra space is used for pointers.

**2. Intersection of Two Linked Lists Leetcode Solution Java**

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; } }

#### 2.1 Explanation

**Variables:****a**and**b**are initialized to**headA**and**headB**respectively.**Traversal:**The**while**loop continues until**a**equals**b**, indicating they have found the intersection node.**Pointer Manipulation:**- If
**a**reaches the end (**null**), it continues from**headB**. - If
**b**reaches the end (**null**), it continues from**headA**.

- If
**Return:**Once**a**equals**b**, they both point to the intersection node, and it is returned.

#### 2.2 Time Complexity

**O(m + n)**, where**m**and**n**are the lengths of**headA**and**headB**respectively. Each pointer might traverse both lists once.

#### 2.3 Space Complexity

**O(1)**, since only a constant amount of extra space is used for pointers.

**3. Intersection of Two Linked Lists Leetcode Solution JavaScript**

var getIntersectionNode = function(headA, headB) { if (!headA || !headB) { return null; } let curA = headA; let curB = headB; while (curA !== curB) { if (curA.next) { curA = curA.next; } else { if (!curB.next) { curA = null; curB = null; break; } curA = headB; } if (curB.next) { curB = curB.next } else { curB = headA; } } return curB; };

#### 3.1 Explanation

**Edge Case:**If either list is empty (**!headA**or**!headB**), return**null**.**Variables:****curA**and**curB**are initialized to**headA**and**headB**respectively.**Traversal:**The**while**loop continues until**curA**equals**curB**, indicating they have found the intersection node.**Pointer Manipulation:**- If
**curA.next**exists, move**curA**to its next node; otherwise, redirect**curA**to**headB**. - If
**curB.next**exists, move**curB**to its next node; otherwise, redirect**curB**to**headA**.

- If
**Return:**Once**curA**equals**curB**, they both point to the intersection node, and it is returned.

#### 3.2 Time Complexity

**O(m + n)**, where**m**and**n**are the lengths of**headA**and**headB**respectively. Each pointer might traverse both lists once.

#### 3.3 Space Complexity

**O(1)**, since only a constant amount of extra space is used for pointers.

**4. Intersection of Two Linked Lists Leetcode Solution Python**

class Solution(object): def getIntersectionNode(self, headA, headB): curA,curB = headA,headB lenA,lenB = 0,0 while curA is not None: lenA += 1 curA = curA.next while curB is not None: lenB += 1 curB = curB.next curA,curB = headA,headB if lenA > lenB: for i in range(lenA-lenB): curA = curA.next elif lenB > lenA: for i in range(lenB-lenA): curB = curB.next while curB != curA: curB = curB.next curA = curA.next return curA

#### 4.1 Explanation

**Variables:****curA**and**curB**are initialized to**headA**and**headB**respectively, to traverse the lists.**Length Calculation:**Count the lengths of both lists using**lenA**and**lenB**.**Adjustment:**- Adjust
**curA**or**curB**to start from the same relative position based on the difference in lengths.

- Adjust
**Traversal:**Traverse both lists simultaneously until**curA**equals**curB**, which indicates the intersection node.**Return:**Return**curA**(or**curB**since they are equal).

#### 4.2 Time Complexity

**O(m + n)**, where**m**and**n**are the lengths of**headA**and**headB**respectively.

#### 4.3 Space Complexity

**O(1)**, since only a constant amount of extra space is used for pointers and variables.