Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Meta coding round for a software engineer position. One linked list problem that looks clean on the surface but has enough edge cases to trip you up if you're not careful about pointer management.

Questions Asked (1)

Given the head of a singly linked list and a value v that appears at least twice, reverse the sublist between the first and second occurrence of v (inclusive), in-place with O(n) time and O(1) space. How do you handle edge cases like adjacent nodes, or when the sublist starts at the head or ends at the tail?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with the standard reverse-sublist approach and felt pretty confident until they asked about the head case.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, traverse the list to locate the first and second occurrences of v, keeping track of the node before the first occurrence (prev_first) and the node after the second occurrence (after_second). Then, reverse the sublist from the first to the second occurrence using the standard iterative three-pointer technique, and reconnect the reversed sublist with prev_first and after_second. Finally, handle edge cases by checking if prev_first is null (sublist starts at head) or if after_second is null (sublist ends at tail) and adjust the head pointer accordingly.

Pro tip: Clarify with the interviewer whether the value v is guaranteed to appear at least twice (as stated) and whether the list can be modified in-place. Also, mention that you would test with edge cases like adjacent occurrences, sublist at head/tail, and list length exactly two.

1. Find the boundaries

Traverse the list to locate the first and second nodes with value v. Keep track of the node before the first occurrence (prev_first) and the node after the second occurrence (after_second).

2. Reverse the sublist

Reverse the sublist from the first to the second occurrence using iterative pointer manipulation. Maintain prev, curr, and next pointers to reverse links without extra space.

3. Reconnect the list

Connect prev_first to the new head of the reversed sublist (which was the second occurrence) and connect the new tail (which was the first occurrence) to after_second.

4. Handle edge cases

If prev_first is null, update the head to point to the new head of the reversed sublist. If after_second is null, ensure the new tail's next is null. For adjacent nodes, the reversal is trivial but still handled by the same logic.

5. Analyze complexity

Explain that the algorithm traverses the list at most twice, so time complexity is O(n). Space complexity is O(1) because only a constant number of pointers are used.

Key Points to Mention

Two-pass approach: first pass to find boundaries, second pass to reverse the sublist.
In-place reversal using three pointers (prev, curr, next) to achieve O(1) space.
Edge case handling: sublist at head (update head pointer), sublist at tail (set next of new tail to null), adjacent nodes (reversal still works).
Time complexity O(n) and space complexity O(1) analysis.
Correct reconnection of the reversed sublist with the rest of the list.
Testing strategy: include cases like v at head, v at tail, adjacent v's, and list with exactly two nodes.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.