LeetCode 206. Reverse Linked List

reverse_linked_list.py

from typing import Optional


"""
LeetCode 206. Reverse Linked List
"""


class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


# O(n) time complexity, O(1) space complexity
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

    prev, current = None, head

    while current:
        tmp = current.next
        current.next = prev
        prev = current
        current = tmp

    return prev


# O(n) time complexity, O(n) space complexity (similar to optimal recursive approach)
def reverseList2(head: Optional[ListNode]) -> Optional[ListNode]:

    node_stack = []

    def list_reverser(head: Optional[ListNode]) -> Optional[ListNode]:
        while head:
            node_stack.append(head)
            head = head.next
        head = tail = None
        while node_stack:
            if not head:
                head = tail = node_stack.pop()
            else:
                tail.next = node_stack.pop()
                tail.next.next = None
                tail = tail.next

        return head

    return list_reverser(head)


# O(n^2) time complexity, O(n) space complexity
def reverseList3(head: Optional[ListNode]) -> Optional[ListNode]:

    def node_append(new_head: Optional[ListNode], node: ListNode) -> Optional[ListNode]:
        current, node.next = new_head, None
        while current:
            if current.next is None:
                current.next = node
                return new_head
            current = current.next

    def list_reverser(head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return
        if head.next is None:
            return head
        return node_append(list_reverser(head.next), head)

    return list_reverser(head)

reverseList3 can be optimized to $O(n)$ time complexity by just keeping pointer to the tail + updating tail upon append rather than using node_append to traverse the newly formed list each time to do an append.