Challenge lab in Linked Lists and Pointer Invariants

Mission

Merge two sorted linked chains without re-sorting.

Learning outcome: Merge two sorted node chains

Correctness contract

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

Required technique: Relink existing nodes from two sorted chains using a dummy head; never copy values into an array and re-sort.

Complexity target: time O(n+m); space O(n+m) nodes.

Input and output

Input: n, then n sorted integers, then m, then m sorted integers. 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:

• Both input sequences are sorted in nondecreasing order.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Relink existing nodes from two sorted chains using a dummy head; never copy values into an array and re-sort.
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 1 4 7 3 2 3 9

Sample output

1 2 3 4 7 9

Why the sample works: Visible walkthrough for the ordinary non-trivial path. The smaller current node is linked next; ties use the first chain, and the final non-empty suffix is attached unchanged. Input `3 1 4 7 3 2 3 9` therefore produces `1 2 3 4 7 9`.

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: When values tie, consume the left input first; this keeps the merge stable.

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.