Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 3 / d

Reuse p as q's header and allocate one new header for r. Cut after

k = ⌊ n /2 ⌋

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