Palindrome Linked List
Real-world version: Stamp Chain EchoThe statement here is our own: the same inputs, outputs and technique.
A packing line stamps one digit on every parcel and clips the parcels into a single chain: each parcel holds its digit plus a clip fastened to the parcel behind it, and the parcel at the end has an empty clip.
Because the harness passes plain JSON, the chain reaches you as the array stamps, listing the digits in clip order starting at the front parcel. There is always at least one parcel.
The line supervisor calls a chain an echo when the digits spell out the same run walked from the front as they do walked from the end.
Return true when the chain is an echo, false otherwise. Work with the clips rather than around them: rebuild the parcels, locate the halfway parcel by moving one cursor forward one parcel at a time and a second cursor two at a time, refasten the clips of the leading half backwards as that cursor passes them, then step outwards from the middle comparing digits. Apart from the parcels themselves, hold only a fixed number of parcel references: no second array, no copied string, no growing stack.
Examples
Example 1
- Input
- stamps = [7, 4, 4, 7]
- Output
- true
Walking from either end gives 7, 4, 4, 7, so the chain is an echo.
Example 2
- Input
- stamps = [9, 3, 5]
- Output
- false
The front parcel is stamped 9 while the end parcel is stamped 5, so the two walks part company immediately.
Example 3
- Input
- stamps = [2, 8, 2]
- Output
- true
The outer parcels agree and the single middle parcel has no partner to match, so the chain is an echo.
Constraints
- The number of parcels in the chain is in the range [1, 10^5].
- 0 <= stamps[i] <= 9
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def stamp_chain_echo(stamps: list[int]) -> bool:public boolean stampChainEcho(int[] stamps)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's