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.
Quick Answer: 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.
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.
Input: ([1], None)
Expected Output: [1]
Explanation: Single node.
Input: ([1, 2, 3, 4], 1)
Expected Output: [4, 3, 2, 1]
Explanation: Cycle policy is break before reverse.
Hints
- Iterative pointer reversal is O(1) extra space; detect cycles first when node references are available.