Application lab in Linked Lists and Pointer Invariants

Mission

Reverse a linked list by rewiring next references.

Learning outcome: Apply pointer reversal iteratively

Correctness contract

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

Required technique: Reverse next references in place with previous, current, and saved-next references.

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

Input and output

Input: n followed by n node values in head-to-tail order. 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.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Reverse next references in place with previous, current, and saved-next references.
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

4 1 2 3 4

Sample output

4 3 2 1

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Every next link is reversed once, making the old tail the new head. Input `4 1 2 3 4` therefore produces `4 3 2 1`.

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: At loop entry, previous is the reversed prefix and current is the first node of the untouched suffix.

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.