LeetCode Solutions Blog

Reverse Linked List

Number: 206

Difficulty: Easy

Paid? No

Problem Description

Reverse a singly linked list. Given the head of a linked list, the task is to reverse the list such that the head becomes the tail and each link is reversed.

Key Insights

The problem can be solved using either an iterative or recursive approach.
Iterative method uses constant space by updating pointers in-place.
Recursive method leverages the call stack to reverse the list, which could use O(n) space in the worst case.
Both approaches traverse each node exactly once, yielding linear time complexity.

Space and Time Complexity

Time Complexity: O(n) for both iterative and recursive approaches, where n is the number of nodes. Space Complexity: O(1) for the iterative approach and O(n) for the recursive approach because of the recursion call stack.

Solution

We can solve the problem by iterating through the list while reversing the next pointers of each node. We maintain two pointers (previous and current) and update them as we traverse the list, so that by the end, the previous pointer is at the new head of the reversed list.

Alternatively, a recursive approach reverses the rest of the list first and then adjusts the pointers so that the original head becomes the tail.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # Store the node value
        self.next = next  # Pointer to the next node

# Iterative approach to reverse the linked list.
def reverseList(head):
    prev = None  # Initially, there is no previous node
    current = head  # Start with the head of the list
    while current:
        next_node = current.next  # Temporarily store the next node
        current.next = prev  # Reverse the current node's pointer
        prev = current  # Move previous pointer one step forward
        current = next_node  # Move to the next node in the list
    return prev  # The new head of the reversed list

# Recursive approach to reverse the linked list.
def reverseListRecursive(head):
    # Base case: empty list or single node
    if not head or not head.next:
        return head
    new_head = reverseListRecursive(head.next)  # Reverse the rest of the list
    head.next.next = head  # Reverse the pointer for the current node
    head.next = None  # Set the next pointer of the current node to None
    return new_head  # Return the new head of the reversed list