In-Place Linked List Reversal | Dataford Interview Questions

Embitel Technologies uses linked structures in components such as navigation and workflow processing. Given the head of a singly linked list, reverse the list in place and return the new head.

You must modify the existing nodes rather than creating replacement nodes. The algorithm must use constant auxiliary space, excluding the input list itself.

Formal Specification

The input is head, either None or a reference to the first ListNode. Each node has:

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

Return a reference to the former tail, which becomes the new head. The relative order of node values must be completely reversed, and every original node must appear exactly once in the result.

Assume the list is acyclic. Do not use arrays, stacks, recursion, or newly allocated list nodes.

Constraints

0 <= n <= 10^5
-10^9 <= node.val <= 10^9
The linked list is singly linked and acyclic
All original nodes must be reused
No arrays, stacks, recursion, or new list nodes may be used

Function Signature

def reverse_linked_list(head):

Your question is In-Place Linked List Reversal. 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