</>EmbeddedInterview

Find the intersection point of two linked lists.

Medium"Coding: Linked Lists, Stacks & Queues"
node_t *intersection(node_t *a, node_t *b)
{
    node_t *p = a, *q = b;
    while (p != q) {
        p = p ? p->next : b;                      /* switch lists at the end */
        q = q ? q->next : a;
    }
    return p;                                     /* meeting node, or NULL if they never meet */
}

Points: after switching heads, both pointers travel len(a) + len(b) steps, so they line up at the intersection (or both become NULL at the same time). O(n + m), O(1) space. Alternative: compute both lengths, advance the longer list by the difference, then walk together. Compare node addresses, not values.