Implementation lab in Linked Lists and Pointer Invariants

Mission

Insert one value before the current linked-list head.

Learning outcome: Implement constant-time head insertion

Correctness contract

Invariant: Every live node is reachable from head exactly once, and the final next reference is null.

Required technique: Create one IntNode, point it at the old head, and publish it as the new head in constant time.

Complexity target: time O(n) input, O(1) insertion; space O(n).

Input and output

Input: n, then n node values in head-to-tail order, then the new head value. Whitespace may be spaces or line breaks.

Output: Print the requested sequence on one line with single spaces and no trailing space. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• n is non-negative and is followed by exactly n signed node values and one inserted value.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Create one IntNode, point it at the old head, and publish it as the new head in constant time.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

3 2 3 4 1

Sample output

1 2 3 4

Why the sample works: Visible walkthrough for the ordinary non-trivial path. The new node points to the old head, so it becomes the first value without changing the remaining links. Input `3 2 3 4 1` therefore produces `1 2 3 4`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Trace the smallest non-trivial input and write the structure state after the operation before coding the loop.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.