= Solution
Reuse `p` as `q`'s header and allocate one new header for `r`. Cut after $k=\lfloor n/2\rfloor$ data elements, allowing $k=0$.
``
PROCEDURE Split(p: List; VAR q, r: List);
VAR n, k, i: INTEGER; last: Tail;
BEGIN
n := p.count; k := n DIV 2;
q := p; NEW(r);
last := q;
FOR i := 1 TO k DO last := last.tail END;
r.tail := last.tail; last.tail := NIL;
q.count := k; r.count := n-k
END Split;
``
The traversal starts at the <dummy header node>, so after $k$ steps `last` precedes the suffix assigned to `r`. Cutting that link produces two finite disjoint <linked lists>. Their concatenated <abstraction function> is the original <list>, with order preserved, and
$$
\boxed{|q|=\lfloor n/2\rfloor,\quad |r|=\lceil n/2\rceil,\quad\alpha(p_{\mathrm{old}}.\mathrm{tail})=\alpha(q.\mathrm{tail})\mathbin{+\!+}\alpha(r.\mathrm{tail}).}
$$
Both empty and singleton inputs work without special traversal cases. The <time complexity> is $O(n)$ and only one header is allocated.
Back to article page
