Practice/LinkedIn/Leetcode 160. Intersection of Two Linked Lists

Leetcode 160. Intersection of Two Linked Lists

CodingOptional

Problem

You are given two singly linked lists. These lists may merge at some point, sharing all subsequent nodes from that point onward. Your task is to identify and return the node where the two lists first converge. If the lists never intersect, return null.

Important: The linked lists share nodes by reference, not just by value. If two lists intersect, they literally point to the same node objects from the intersection point forward.

Requirements

1. Return the reference to the first shared node, or null if no intersection exists
2. The linked lists must remain unmodified after your function executes
3. You cannot change the values stored in the nodes
4. Your solution should handle lists of different lengths

Constraints

• The number of nodes in each list is in the range [0, 3000]
• Node values are between -100000 and 100000
• Your solution should aim for O(m + n) time complexity where m and n are the lengths of the two lists
• Your solution should aim for O(1) space complexity

Examples

Example 1:

Input: ListA: 4 → 1 → 8 → 4 → 5 ListB: 5 → 6 → 1 → 8 → 4 → 5 (The node with value 8 is where they intersect) Output: Node with value 8 Explanation: The lists merge at the node containing 8, and share all nodes after that point.

Example 2:

Input: ListA: 2 → 6 → 4 ListB: 1 → 5 Output: null Explanation: These lists never intersect, so we return null.

Example 3:

Input: ListA: 3 ListB: 2 → 3 (The node with value 3 is shared) Output: Node with value 3 Explanation: ListB's second node is the same node as ListA's only node.