Domain 1EasyCORE

Reverse Linked List

The problem requires reversing a singly linked list given its head node. The input is the head of the linked list, and the output should be the head of the reversed linked list. The constraints indicate that the number of nodes in the list can range from 0 to 5000, with each node's value ranging from -5000 to 5000.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Linked List

206. Reverse Linked List

Model: qwen2.5-coder:14b
Topics: Linked List
FAANG asked: 1
Acceptance rate: 65.7%


Problem Breakdown

The problem requires reversing a singly linked list given its head node. The input is the head of the linked list, and the output should be the head of the reversed linked list. The constraints indicate that the number of nodes in the list can range from 0 to 5000, with each node’s value ranging from -5000 to 5000.

Key edge cases include:

  • An empty list (head is None).
  • A single-node list.
  • Lists with duplicate values.

Intuition

A brute-force approach would involve creating a new linked list and inserting nodes at the beginning. However, this requires additional space proportional to the number of nodes, making it inefficient in terms of both time and space complexity.

The key insight is to reverse the links between nodes in place. This can be done iteratively or recursively. The iterative approach involves maintaining three pointers: prev, current, and next. By iterating through the list and adjusting these pointers, we can reverse the links without using extra space.

Approach

We will implement both iterative and recursive solutions for reversing a linked list.

Iterative Approach:

  1. Initialize three pointers: prev as None, current as head, and next as None.
  2. Iterate through the list until current becomes None.
  3. In each iteration, set next to current.next, then reverse the link by setting current.next to prev.
  4. Move prev to current and current to next.
  5. After the loop, prev will be pointing to the new head of the reversed list.

Recursive Approach:

  1. Base case: If head is None or head.next is None, return head.
  2. Recursively call the function on head.next to reverse the rest of the list.
  3. Adjust the links by setting head.next.next to head and head.next to None.
  4. Return the new head obtained from the recursive call.

Complexity Analysis

  • Time Complexity: O(n) for both iterative and recursive approaches, where n is the number of nodes in the linked list.
  • Space Complexity: O(1) for the iterative approach (constant space). For the recursive approach, the space complexity is O(n) due to the call stack.

Solution

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Iterative Approach
    def reverseListIterative(self, head: ListNode) -> ListNode:
        prev = None
        current = head
        while current:
            next_node = current.next  # Store next node
            current.next = prev       # Reverse current node's pointer
            prev = current            # Move pointers one position ahead
            current = next_node
        return prev

    # Recursive Approach
    def reverseListRecursive(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        new_head = self.reverseListRecursive(head.next)
        head.next.next = head
        head.next = None
        return new_head

Edge Cases Handled

  • Empty List: Both functions handle an empty list by returning None.
  • Single Node List: The iterative approach naturally handles this case, while the recursive approach returns the single node as is.
  • Lists with Duplicate Values: The reversal process does not depend on the values of the nodes, so duplicates are handled correctly.