Katkat
Back

Reverse a Singly Linked List

GrammarlySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your understanding of pointer manipulation and iterative/recursive techniques for modifying linked structures in-place.

Problem Statement

Given a singly linked list represented as a nested structure of two-item lists, reverse the list in-place. Each node is represented as [value, next_node], where next_node is either another list node or None if it is the end of the chain.

You must reverse the list by modifying the existing node references. You are not allowed to create new node objects or lists.

Function Signature

def reverse_list(head):

Constraints

  • The input head is a nested list structure or None.
  • Your solution should operate in O(n) time complexity.
  • Your solution should operate in O(1) auxiliary space.

Examples

Example 1: Input: [1, [2, [3, None]]] Output: [3, [2, [1, None]]]

Example 2: Input: None Output: None

Edge Cases

  • Empty lists (None).
  • Single-node lists ([5, None]).
  • Very long chains (ensure your solution does not hit recursion limits if you choose a recursive approach).

Hints

Hint 1

To reverse the list, you need to keep track of the current node, the previous node, and the next node before you modify the current node's pointer.

Hint 2

Initialize two pointers, `prev` as `None` and `curr` as `head`, then iterate through the structure until `curr` is `None`.

Hint 3

In each step of the iteration, save the next node, redirect the `curr` node's pointer to `prev`, and then shift `prev` and `curr` forward.

Follow-up questions

  • How would your implementation change if you were asked to implement this using a recursive approach instead of an iterative one?
  • What are the space complexity trade-offs between an iterative approach and a recursive approach for this problem?
  • How would you modify your algorithm to reverse only a sub-segment of the list between position `m` and `n`?