Genetic Signal Ring Shifts
Rotate each nonzero linked-list block right by its value sum
A genetics lab stores a sequence of signal readings in a singly linked list. Nodes with value 0 are fixed separators. Each maximal consecutive block of nonzero nodes is a fragment.
For each fragment, compute the sum s of its original node values and its length m. Rotate that fragment to the right by s positions. A negative shift means rotating to the left by -s positions. Shifts wrap around: equivalently, rotate right by the unique integer r satisfying 0 <= r < m and r ≡ s (mod m).
A right rotation by one position moves the fragment's last node to its beginning. Separator nodes must remain between the same neighboring fragments, and every fragment is processed independently. A fragment may begin at the head or end at the tail; consecutive separators do not create any nodes to process.
Return the head of the resulting linked list. Reuse the existing nodes without changing their values, using O(1) auxiliary space.
Examples
Example 1
Input: head = [1,2,1,0,4,-1] Output: [1,1,2,0,-1,4]
The first fragment has sum 4 and length 3, so its last node moves to the front. The separator stays between the fragments. The second fragment has sum 3 and length 2, so it also rotates right by one.
Example 2
Input: head = [-4,1,2] Output: [1,2,-4]
The fragment has sum -1 and length 3. Rotating right by -1 is the same as rotating left by one.
Example 3
Input: head = [0,0,7,0] Output: [0,0,7,0]
Leading, trailing, and consecutive separators stay in place. The only fragment has length one, so its rotation cannot change the chain.
Constraints
- The linked list contains between 0 and 12,000 nodes.
- Each node value is an integer between -100 and 100, inclusive.
- The input linked list is acyclic.
The intended solution takes O(n) time and O(1) auxiliary space. In JavaScript, normalize a negative remainder before using it as the rotation amount.
Hints
Show hint 1Hint 1
For each fragment, find its last node, length, sum, and the node immediately after it before changing any links.
Show hint 2Hint 2
A nontrivial rotation can be performed by connecting the fragment's tail to its head, then breaking that temporary cycle at the new tail.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you adapt the pointer operations if every fragment's shift were supplied separately instead of computed from its values?
- Can you perform the same transformation on a circular linked list when a designated separator defines the starting point?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem