Linked List Head Identification | Dataford Interview Questions

The PlayStation Store uses ordered navigation history entries for certain UI flows. Given the head of a singly linked list containing these entries, reverse the list in place and return the new head.

Your function receives a ListNode object. Each node has an integer val and a next reference, or None for the end of the list. Do not create replacement nodes or use an array to store the values. The test cases represent linked lists as arrays, and the test harness converts each array into a ListNode chain before calling the function. The returned list is serialized back to an array.

Formal Specification

Implement reverse_linked_list(head), where head is a ListNode or None. Return the new head after reversing every next pointer. The original nodes must be reused.

Constraints

0 <= n <= 10^5, where n is the number of nodes
-10^9 <= node.val <= 10^9
The list contains no cycles
The reversal must reuse the existing nodes

Function Signature

def reverse_linked_list(head):

Your question is Linked List Head Identification. Start with the requirements in the Question tab.

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

Problem