Skip to main content

🟩 Reverse Linked List (#206)

🔗 Problem Link​

📋 Problem Statement​

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

💡 Examples​

Example 1​

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2​

Input: head = [1,2]
Output: [2,1]

Example 3​

Input: head = []
Output: []

🔑 Key Insights & Approach​

Core Observation: Reverse pointers iteratively while maintaining three pointers: prev, current, and next.

Why Iterative Three Pointers?

  • O(n) time, O(1) space
  • Simple and intuitive
  • No stack overflow risk unlike recursion

Approaches:

  1. Iterative with three pointers: O(n) time, O(1) space - optimal
  2. Recursive: O(n) time, O(n) space (call stack)

Pattern: "Linked List Reversal" pattern with pointer manipulation.

🐍 Solution: Python​

Approach 1: Iterative​

Time Complexity: O(n) | Space Complexity: O(1)

from typing import Optional

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

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        current = head

        while current:
            # Save next node
            next_node = current.next

            # Reverse the link
            current.next = prev

            # Move pointers forward
            prev = current
            current = next_node

        return prev

Approach 2: Recursive​

Time Complexity: O(n) | Space Complexity: O(n)

from typing import Optional

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        # Reverse rest of list
        new_head = self.reverseList(head.next)

        # Reverse current node
        head.next.next = head
        head.next = None

        return new_head

🔵 Solution: Golang​

Approach: Iterative​

Time Complexity: O(n) | Space Complexity: O(1)

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    current := head

    for current != nil {
        // Save next
        nextNode := current.Next

        // Reverse link
        current.Next = prev

        // Move forward
        prev = current
        current = nextNode
    }

    return prev
}

📚 References​