Reverse linked lists, including k-group

Q: Reverse linked lists, including k-group

This question evaluates understanding of linked list manipulation including pointer operations, in-place reversal techniques, recursion and stack-depth considerations, cycle detection, and time/space complexity analysis.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during HR Screen rounds at NVIDIA.

Q: What role is this question designed for?

This question is commonly asked for Data Scientist candidates at NVIDIA during technical interviews.

Question

Singly Linked List Reversal — Variants and Edge Cases

You are given a standard singly linked list with nodes of the form:

Node fields: value, next
Head pointer may be null (empty list).
Assume 1-indexed positions for m and n.

Implement and analyze the following:

A) Reverse Entire List

Provide an iterative in-place solution that uses O(1) extra space.
Provide a recursive solution.
Analyze time and space complexity of both.
Explicitly handle edge cases: empty list, single-node list, and very long lists (stack depth considerations for recursion).

B) Reverse a Sublist [m, n]

Reverse the nodes from position m to n (inclusive), in-place, and return the head. Assume 1 ≤ m ≤ n ≤ length of list.

C) Reverse Nodes in k-Groups

Reverse the list in contiguous groups of size k using O(1) extra space. If the final group has fewer than k nodes, leave that tail group as-is.

D) Cycle Detection Before Reversal

Explain and implement how to detect a cycle in the list and reject (do not attempt to reverse) if a cycle is present.

You may use pseudo-code or code in a language of your choice.

Reverse linked lists, including k-group

Quick Overview

Reverse linked lists, including k-group

Singly Linked List Reversal — Variants and Edge Cases

A) Reverse Entire List

B) Reverse a Sublist [m, n]

C) Reverse Nodes in k-Groups

D) Cycle Detection Before Reversal

Submit Your Answer to Earn 20XP