سوال ۶۷ کنکور ارشد علوم کامپیوتر ۱۳۹۸

What the algorithm builds

List $z$ is formed by alternately interleaving nodes of $X$ and $Y$ — $x_1, y_1, x_2, y_2, \ldots$ — and the alternation continues only as far as the shorter list allows. Let $k = \min(m, n)$. After $k$ interleaved pairs, one list is exhausted and the remaining suffix of the longer list is appended.

Why it is $O(\min(m, n))$, not $O(m + n)$

The lists are singly linked, so combining them is done by pointer splicing, not by copying values.

• Interleaving phase. To weave $x_1, y_1, x_2, y_2, \ldots, x_k, y_k$ we rewire the next pointers of the first $2k$ nodes. Each redirection is $O(1)$, and there are $2k = 2\min(m, n)$ of them, so this phase costs $\Theta(\min(m, n))$.

• Append phase. When the shorter list runs out, the rest of the longer list (the nodes $x_{k+1}, \ldots$ or $y_{k+1}, \ldots$) is already a correctly ordered chain. We do not need to walk it — at the point of exhaustion we are sitting on the node whose next pointer still points to that suffix's head, so the suffix stays attached automatically (or is spliced with a single assignment). This is $O(1)$.

The loop stops the moment the shorter list ends, so the number of iterations is governed by $\min(m, n)$:

$T = \underbrace{\Theta(\min(m,n))}_{\text{interleave } 2\min(m,n)\text{ nodes}} + \underbrace{O(1)}_{\text{splice the longer tail}} = O(\min(m, n)).$

Eliminating the distractors

Exam trick: On linked lists, "append the rest of the longer list" is an $O(1)$ splice — the work is bounded by where the alternation stops, i.e. $\min(m,n)$. Reflexively answering $O(m+n)$ is the array-thinking mistake.