206. Reverse Linked List
Standard reverse a linked list question. Implemented both iteratively and recursively.
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
node = head
prev = None
while node != None:
next_node = node.next
node.next = prev
prev = node
node = next_node
return prev
Time complexity: O(n)
Space complexity: O(1)
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def helper(head, prev):
if not head:
return prev
temp = head.next
head.next = prev
return helper(temp, head)
return helper(head, None)
Time complexity: O(n)
Space complexity: O(n) - recursive stack is the size of the linked list
Last modified 1yr ago