Reverse Linked List and Hash Map | Dataford Interview Questions

Your question is Reverse Linked List and Hash Map. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Telesign Verify can represent an ordered chain of verification attempts as a singly linked list. Given the head of such a list, reverse the list using a hash map to preserve each node's original successor before changing any next pointers.

Return the new head after reversal. The nodes must be reused rather than copied.

Formal Specification

The input is head, either None or a ListNode with:

value, an integer payload
next, a reference to the next ListNode or None

Return a ListNode that is the head of the reversed chain. The input list may contain zero or more nodes and is acyclic. In the serialized examples and test cases, lists are represented as arrays of node values.

Constraints

0 <= n <= 10^5
-10^9 <= node.value <= 10^9
The list is singly linked and acyclic
Reuse the existing nodes
A hash map must be used to preserve original successor references

Function Signature

def reverse_linked_list(head):