We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reverse Linked List

Difficulty: Easy

Problem Description

Given the head of a singly linked list, reverse the list, and return the reversed list.

Key Insights

  • The problem involves reversing a linked list, which can be approached iteratively or recursively.
  • A linked list consists of nodes where each node points to the next node, making traversal straightforward but reversal more complex.
  • Edge cases include empty lists and lists with a single node.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list, as we need to traverse the entire list. Space Complexity: O(1) for the iterative solution (in-place reversal) and O(n) for the recursive solution due to the call stack.

Solution

To reverse a singly linked list, we can use two main approaches: iterative and recursive.

  1. Iterative Approach:

    • We initialize three pointers: prev, current, and next.
    • We traverse the list, reversing the pointers one by one until we reach the end.
    • Finally, prev will point to the new head of the reversed list.

  2. Recursive Approach:

    • We can use recursion to reverse the linked list by reversing the rest of the list and then adjusting the pointers.
    • The base case is when we reach the end of the list (null or single node).
    • We adjust the pointers during the unwinding of the recursion stack.

Code Solutions

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

def reverseList(head: ListNode) -> ListNode:
    prev = None
    current = head
    while current:
        next = current.next  # Store next node
        current.next = prev  # Reverse the link
        prev = current       # Move prev to current
        current = next       # Move to next node
    return prev  # New head of the reversed list
← Back to All Questions