Reverse sublist between equal-value nodes
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given the head of a singly linked list and a target value v that appears at least twice, reverse the sublist starting at the first node with value v and ending at the second node with value v (inclusive). If v appears fewer than two times, return the original list. Provide an in-place O(n) time, O(
1) extra space solution and discuss edge cases (adjacent boundaries, when the sublist includes the head or tail).
Quick Answer: This question evaluates linked-list manipulation and pointer-management skills, focusing on reversing an in-place sublist between two nodes with equal values while respecting O(n) time and O(1) extra space constraints.
You are given a singly linked list (represented here as an array `values` of its node values) and a target value `v`. The value `v` is guaranteed to appear at least twice in a valid reversal scenario, but your code must handle the case where it appears fewer than two times.
Reverse the sublist that starts at the FIRST node whose value equals `v` and ends at the SECOND node whose value equals `v` (inclusive). Return the resulting list of node values.
If `v` appears fewer than two times, return the original list unchanged.
Your algorithm should run in O(n) time and use O(1) extra space (pointer manipulation only — do not allocate a second list). The array representation is only the I/O wrapper; internally you should reason about it as a linked list.
Example 1:
values = [1, 2, 3, 4, 2, 5], v = 2
First 2 is at index 1, second 2 is at index 4. Reverse the segment [2, 3, 4, 2] -> [2, 4, 3, 2].
Result: [1, 2, 4, 3, 2, 5]
Example 2:
values = [2, 3, 4, 5, 2], v = 2
The sublist spans the whole list (head to tail). Reverse [2, 3, 4, 5, 2] -> [2, 5, 4, 3, 2].
Result: [2, 5, 4, 3, 2]
Example 3:
values = [7, 8, 9], v = 3
3 does not appear, so return the list unchanged: [7, 8, 9].
Constraints
- 0 <= number of nodes <= 10^5
- -10^9 <= node value, v <= 10^9
- Solution must be in-place (O(1) extra space): only pointer rewiring, no second list
- If v appears fewer than two times, return the list unchanged
Examples
Input: ([1, 2, 3, 2, 4], 2)
Expected Output: [1, 2, 3, 2, 4]
Explanation: First 2 at index 1, second 2 at index 3. Sublist [2,3,2] reversed is [2,3,2] (palindromic segment), so the list is unchanged.
Input: ([1, 2, 3, 4, 2, 5], 2)
Expected Output: [1, 2, 4, 3, 2, 5]
Explanation: First 2 at index 1, second 2 at index 4. Reverse [2,3,4,2] -> [2,4,3,2], giving [1,2,4,3,2,5].
Hints
- Use a dummy node before the head so that reversing a sublist that includes the original head is handled uniformly with the general case.
- First scan to locate the first node equal to v (and remember the node immediately before it). Then continue scanning from the node after it to find the second node equal to v.
- Reverse the segment [first .. second] using the standard prev/cur pointer-reversal loop, but initialize prev to the node AFTER the second occurrence so the reversed segment links correctly to the tail. Finally point prev_first.next at the second node (the new front of the reversed segment).
- Edge cases: if either occurrence is missing, return unchanged. Adjacent boundaries (the two v-nodes are neighbors or equal-valued with nothing between) reverse to themselves, which the same loop handles.