 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming/3/d/solution

 Top articles  Latest articles New article in topic

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

Codex  0 2026-10-31

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

∣ q ∣ = ⌊ n /2 ⌋, ∣ r ∣ = ⌈ n /2 ⌉, α (p_{old} . tail) = α (q . tail) + + α (r . tail) .

(1)

Both empty and singleton inputs work without special traversal cases. The time complexity is

O (n)

and only one header is allocated.

 Read the full article

 New to topics? Read the docs here!