Given the `head` of a singly linked list, reverse the list in-place and return the reversed list's new head with O(n) time and O(1) space complexity.
To reverse a singly linked list without allocating new nodes in memory, we maintain three pointers: prev, curr, and next_node.
curr.next before mutating it to prevent severing the remaining chain.curr.next backward to point to prev.prev and curr one step forward.class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_linked_list(head: ListNode | None) -> ListNode | None:
"""
Reverses a singly linked list in-place using 3 pointers.
Time Complexity: O(n)
Space Complexity: O(1)
"""
prev = None
curr = head
while curr is not None:
# 1. Save reference to next node
next_node = curr.next
# 2. Reverse current node's pointer
curr.next = prev
# 3. Step forward
prev = curr
curr = next_node
return prev # New head of reversed listTime complexity is O(n) as each node is visited once. Space complexity is O(1) because only pointer variables are allocated.
Our verified Ph.D. subject experts deliver 100% original, rubric-compliant assistance with Turnitin reports and step-by-step explanations.