206. Reverse Linked List

Description

See: https://leetcode.com/problems/reverse-linked-list/

Solution

Standard reverse a linked list question. Implemented both iteratively and recursively.

Iterative

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)

Recursive

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