Reverse a singly linked list robustly
Company: NVIDIA
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: HR Screen
Reverse a singly linked list in place. Provide: 1) An iterative O(1)-extra-space solution and a recursive version; explain how you avoid stack overflow for up to 10^6 nodes (tail recursion elimination or chunked recursion). 2) Handling of edge cases: empty list, single node, very long list. 3) Behavior on cyclic lists: detect a cycle (Floyd’s) and either preserve the cycle orientation while reversing the linear segment or break the cycle—justify your choice and implement accordingly. 4) Time/space analysis, loop invariant for correctness, and minimal set of tests.
Overview: This question evaluates linked-list manipulation skills including in-place iterative reversal, recursive techniques, cycle detection and handling, time and space complexity analysis, loop invariants, and minimal test design.
Read the full NVIDIA Data Scientist interview experience this question came from
Reverse a linked list represented by values; if a cycle position is supplied, the policy is to break the cycle before reversal.
Examples
Input: ([1, 2, 3], None)
Expected Output: [3, 2, 1]
Explanation: Basic reversal.
Input: ([], None)
Expected Output: []
Explanation: Empty list.
Hints
- Iterative pointer reversal is O(1) extra space; detect cycles first when node references are available.