Difficulty: Easy · LeetCode 206

Problem

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

Understanding the problem

Invert all next pointers.

Intuition

Iterative three pointers: previous, current, next_node.

Approach

Initialize previous = None, current = head.
While current exists:
Save next_node = current.next.
Reverse pointer: current.next = previous.
Advance previous = current, current = next_node.
Return previous as new head.

Naive Solution — Brute Force

Recursive call stack reversal.

Python

class Solution:
    def reverseList(self, head):
        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

C++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }

        ListNode* newHead = reverseList(head->next);

        head->next->next = head;
        head->next = nullptr;

        return newHead;
    }
};

Java

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode newHead = reverseList(head.next);

        head.next.next = head;
        head.next = null;

        return newHead;
    }
}

JavaScript

var reverseList = function(head) {
    if (!head || !head.next) {
        return head;
    }

    const newHead = reverseList(head.next);

    head.next.next = head;
    head.next = null;

    return newHead;
};

Time: O(n) · Space: O(n) stack

Optimized Code (Python 3)

Python

class Solution:
    def reverseList(self, head):
        previous = None
        current = head

        while current:
            next_node = current.next

            current.next = previous

            previous = current
            current = next_node

        return previous

C++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* previous = nullptr;
        ListNode* current = head;

        while (current) {
            ListNode* nextNode = current->next;

            current->next = previous;

            previous = current;
            current = nextNode;
        }

        return previous;
    }
};

Java

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        ListNode current = head;

        while (current != null) {
            ListNode nextNode = current.next;

            current.next = previous;

            previous = current;
            current = nextNode;
        }

        return previous;
    }
}

JavaScript

var reverseList = function(head) {
    let previous = null;
    let current = head;

    while (current) {
        const nextNode = current.next;

        current.next = previous;

        previous = current;
        current = nextNode;
    }

    return previous;
};

Time: O(n) · Space: O(1)

Takeaway

Pattern — Three pointers: previous → current → next