EASY
DATA STRUCTURES AND ALGORITHMS

# How to Solve Intersection of Linked List

Written By ## Intersection of Linked List Introduction

The Intersection of linked list problem (also known as the Intersection of two linked list problem) asks us to return the node at which two linked lists intersect, if none then we return None. This problem requires us to consider the lengths of the given linked lists before using our pointers. Using the lengths we can adjust our starting positions accordingly. By using these two pointers effectively to traverse the lists we can find the point in which they intersect without comparing every node.

## Intersection of Linked List 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 none.

## Intersection of Linked List Solutions

We can solve this problem using two-pointers. We start by finding the lengths of the two linked lists and adjust the starting positions of the pointers accordingly. This step ensures that both pointers are at the same relative position from the end of their respective lists. Next, we traverse the linked lists simultaneously using the two pointers. We keep moving the pointers one node at a time until either they meet at an intersection point or both reach the end of their lists. By doing this, we can search for the intersection point without having to compare every node.

If the pointers meet, it means we have found the intersection point. We can return that node as the result. If the pointers reach the end of their lists without meeting, it let's us know that there is no intersection between the two linked lists. In this case, we return 'None' to signify the absence of an intersection.

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

# Check if either list is empty
return None

# Get the lengths of both lists
lenA, lenB = 0, 0
while nodeA:
lenA += 1
nodeA = nodeA.next
while nodeB:
lenB += 1
nodeB = nodeB.next

# Move the longer list's head pointer to align the lengths
while lenA > lenB:
lenA -= 1
while lenB > lenA:
lenB -= 1

# Traverse both lists to find the intersection point

# Return the intersection node (or None if no intersection)

# Create linked lists for testing
# Intersection point at node with value 8
common = ListNode(8, ListNode(4, ListNode(5)))
headB = ListNode(5, ListNode(6, ListNode(1, common)))

# Test our solution
if intersection:
print("Intersection at node with value:", intersection.val)
else:
print("No intersection")

#Expected output: 8``````

#### Time/Space Complexity Analysis

• Time Complexity: O(m + n), where m and n are the lengths of the two linked lists. We need to traverse both lists to calculate their lengths and then traverse them again simultaneously until we find the intersection point or reach the end. This means that the time complexity is linear with respect to the lengths of the lists.
• Space Complexity: O(1), as we only use a constant amount of extra space to store the two pointers and a few other variables.