206. Reverse Linked List
Summary
Given the head of a singly linked list, reverse the list, and return the reversed list.
Approach
Recursion.
The new head will be the current tail. We can reverse the pointers like this:
node.next.next = node
node.next = None
Function
Function reverse(node):
If node is None or node.next is None:
return node
new_head = reverse(node.next)
node.next.next = node
node.next = None
return new_head
Complexity
Time Complexity: O(N)
Space Complexity: O(N)
Approach
Iterative.
Keep track of the previous node and the current node. Then reverse the pointer with current.next = prev.
Function
Initialization:
current = headprev = None
While current:
before_rev = current.next
current.next = prev
prev = current
current = before_rev
Return prev.
Complexity
Time Complexity: O(N)
Space Complexity: O(1)