How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at LinkedIn.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at LinkedIn during technical interviews.

Detect intersection of two linked lists | LinkedIn Coding Question

Detect intersection of two linked lists

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given two singly linked lists that may converge to share a common tail, determine whether they intersect and return the first node at which they join. Nodes are compared by reference, not by value. Aim for O(m+n) time and O( 1) extra space. Describe and implement an approach, justify its correctness, and analyze time and space complexity. Discuss edge cases such as one empty list, no intersection, and very unequal lengths.

Quick Answer: This question evaluates a candidate's ability to manipulate singly linked lists, reason about pointer and reference equality between nodes, and perform algorithmic analysis of time and space trade-offs.

Two singly linked lists may converge and share a common tail. Two nodes are considered the same only when they are the same node by reference (identity), never merely by equal value. Determine whether the two lists intersect and return the value of the first node at which they join, or report no intersection. Because raw pointer-based linked lists cannot be passed directly to your function, the two lists are described by three value arrays: - prefixA: the values of the nodes that are unique to list A (its prefix before the intersection). - prefixB: the values of the nodes that are unique to list B (its prefix before the intersection). - sharedTail: the values of the shared suffix, i.e. the intersection node and everything after it. The SAME physical nodes are appended to the end of both prefixes. An empty sharedTail means the two lists do NOT intersect (each list is just its own prefix, ending in null). Reconstruct the two lists from these arrays (appending the same shared-tail node objects to both prefixes), then return the value of the first shared node, or null/None if the lists do not intersect. Aim for O(m + n) time and O(1) extra space, where m and n are the list lengths. Note that comparing by value would be incorrect (the equal-value, non-intersecting example demonstrates why); you must compare by node identity. Classic two-pointer idea: advance one pointer through each list; when a pointer reaches the end, redirect it to the head of the other list. After at most m + n steps both pointers have traversed prefixA + sharedTail + prefixB (and symmetrically), so they meet at the first shared node if one exists, or both reach null simultaneously if not.

Constraints

0 <= len(prefixA), len(prefixB) <= 30000
0 <= len(sharedTail) <= 30000
An empty sharedTail means the two lists do not intersect.
Node values fit in a 32-bit signed integer.
Nodes are compared by reference (identity), not by value.
Target O(m + n) time and O(1) extra space.

Examples

Input: ([1, 2, 3], [6, 7], [4, 5])

Expected Output: 4

Explanation: List A is 1->2->3->4->5 and list B is 6->7->4->5; they merge at the node with value 4, which is the first shared node.

Input: ([1, 9, 1], [3], [2, 4])

Expected Output: 2

Explanation: List A is 1->9->1->2->4 and list B is 3->2->4; the shared tail starts at value 2, so the first intersection node is 2.

Input: ([2], [1, 5], [])

Expected Output: None

Explanation: Empty shared tail means the lists do not intersect: A is 2 and B is 1->5, ending in their own nulls.

Input: ([], [], [8, 9])

Expected Output: 8

Explanation: Both prefixes are empty, so both heads ARE the shared tail 8->9; the first (and entire) shared node is 8.

Input: ([1, 2, 3, 4, 5], [], [])

Expected Output: None

Explanation: List B is empty (no nodes) and there is no shared tail, so there is nothing to intersect; return None.

Input: ([], [7, 7], [])

Expected Output: None

Explanation: List A is empty and the shared tail is empty, so no intersection exists even though B has repeated values.

Input: ([4, 1, 8, 4, 5], [5, 6, 1, 8, 4, 5], [])

Expected Output: None

Explanation: Both lists contain equal values (...,1,8,4,5) but share no physical node because the shared tail is empty; identity comparison correctly returns None, whereas a value comparison would wrongly report a match.

Input: ([1000000], [], [-3])

Expected Output: -3

Explanation: List A is 1000000->-3 and list B is just the shared tail -3; the first shared node has value -3, exercising large and negative values.

Hints

Comparing nodes by value is wrong: two lists can contain identical values yet never share a physical node. You must compare by node identity.
If the lists have lengths m and n, the part after the intersection has the same length for both. The difference m - n comes entirely from the unique prefixes.
Two-pointer trick: walk pointer A through list A then continue into list B, and pointer B through list B then into list A. Both travel m + n steps, so they align at the first shared node — or both hit null together when there is no intersection.
Handle the empty-list case first: if either reconstructed list is empty, there can be no intersection.

Quick Overview

This question evaluates a candidate's ability to manipulate singly linked lists, reason about pointer and reference equality between nodes, and perform algorithmic analysis of time and space trade-offs.