Solution 1 - Iterative (Two Pointers)

Use two pointers, prev and curr, to traverse the list. At each step, save the next node, reverse the current node's pointer to point to prev, then advance both pointers forward. When curr becomes None, prev is the new head of the reversed list.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0206.1 - Reverse Linked List - Solution 1 - Iterative (Two Pointers) """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class ListNode:
    """ListNode Class"""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """Solution Class"""

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """Reverse Linked List Function"""
        prev = None
        curr = head

        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp

        return prev


#####################################################################################
# Functions
#####################################################################################
def build_list(vals):
    """Helper to build a linked list from a list of values"""
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def to_list(head):
    """Helper to convert a linked list to a list"""
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result


def testcase():
    """Test Function"""
    print(to_list(Solution().reverseList(build_list([1, 2, 3, 4, 5]))))  # [5, 4, 3, 2, 1]
    print(to_list(Solution().reverseList(build_list([1, 2]))))            # [2, 1]
    print(to_list(Solution().reverseList(build_list([]))))                # []


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Recursive

Recursively reverse the rest of the list starting from head.next. Once the recursion returns the new head, set head.next.next to point back to head, and set head.next to None to avoid cycles. The base case is when the list is empty or has one node.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0206.2 - Reverse Linked List - Solution 2 - Recursive """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class ListNode:
    """ListNode Class"""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """Solution Class"""

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """Reverse Linked List Function"""
        if not head or not head.next:
            return head

        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return new_head


#####################################################################################
# Functions
#####################################################################################
def build_list(vals):
    """Helper to build a linked list from a list of values"""
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def to_list(head):
    """Helper to convert a linked list to a list"""
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result


def testcase():
    """Test Function"""
    print(to_list(Solution().reverseList(build_list([1, 2, 3, 4, 5]))))  # [5, 4, 3, 2, 1]
    print(to_list(Solution().reverseList(build_list([1, 2]))))            # [2, 1]
    print(to_list(Solution().reverseList(build_list([]))))                # []


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0206 - Reverse Linked List

Solution 1 - Iterative (Two Pointers)

Solution 2 - Recursive