Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0206 - Reverse Linked List
    0206 - Reverse Linked List
    0206 - Reverse Linked List
    0206 - Reverse Linked List

    0206 - Reverse Linked List

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/reverse-linked-list/

    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)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    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)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 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()

    """ 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()