Intersection of Two Linked Lists

This challenge asks you to identify the intersection point of two singly linked lists. Finding the intersection point is a common problem in data structures and algorithms, useful in scenarios like merging data from multiple sources or representing relationships between entities. Your task is to determine the node where the two lists meet, if an intersection exists.

Problem Description

You are given two singly linked lists, headA and headB. Both lists are non-empty and contain distinct nodes except for the intersection point. The intersection point is a node that exists in both lists. Your goal is to find the intersection node. If there is no intersection, return null (or equivalent in your chosen language).

What needs to be achieved:

• Determine if the two linked lists intersect.
• If they intersect, return the node where they intersect.
• If they do not intersect, return null.

Key Requirements:

• The linked lists are singly linked.
• Nodes in each list are distinct except for the intersection point.
• The intersection point is a node that exists in both lists.
• The lists may have different lengths.

Expected Behavior:

The function should traverse both linked lists and compare each node to see if it exists in both lists. If a common node is found, that node is the intersection point and should be returned. If the end of either list is reached without finding a common node, then there is no intersection, and null should be returned.

Edge Cases to Consider:

• Empty lists (although the problem states they are non-empty, it's good to consider).
• Lists with no intersection.
• Lists with a long intersection point far down the lists.
• Lists of significantly different lengths.

Examples

Example 1:

Input:
headA: 4 -> 1 -> 8 -> 4 -> 5
headB: 5 -> 6 -> 1 -> 8 -> 4 -> 5
Intersection Point: 8

Output: 8 Explanation: The two lists share a common node starting with the value 8.

Example 2:

Input:
headA: 1 -> 9 -> 1 -> 2 -> 4
headB: 3 -> 2 -> 4
Intersection Point: 2

Output: 2 Explanation: The two lists share a common node starting with the value 2.

Example 3:

Input:
headA: 1 -> 2 -> 3
headB: 4 -> 5 -> 6

Output: null Explanation: The two lists do not intersect.

Example 4:

Input:
headA: 1 -> 2
headB: 2

Output: 2 Explanation: The two lists intersect at the node with value 2.

Constraints

• The number of nodes in each linked list is between 1 and 1000.
• The values of the nodes are integers.
• The intersection point, if it exists, will be a node that is present in both lists.
• The time complexity should be O(m + n), where m and n are the lengths of the two linked lists.
• The space complexity should be O(1) (constant space).

Notes

Consider using a technique that leverages the lengths of the linked lists to efficiently find the intersection point. You don't need to modify the original linked lists. Think about how you can align the starting points of the two lists before comparing nodes. A common approach involves first calculating the lengths of both lists and then advancing the pointer of the longer list by the difference in lengths. This ensures that both pointers are the same distance from the potential intersection point. After alignment, you can iterate through both lists simultaneously, comparing nodes until you find a match or reach the end of both lists.