Reverse Linked List

Updated on 03 July, 2025
Reverse Linked List header image

Problem Statement

The task requires developing a solution to reverse a singly linked list. A linked list is a linear collection of data elements, where each element points to the next. Each element, or node, contains some data and a reference to the next node in the sequence. If you receive the head of such a list, the goal is to reorient the nodes such that the head becomes the last element and the original last element becomes the first, effectively reversing the direction the nodes point. The reversed linked list should then be returned.

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:

[]

Constraints

  • The number of nodes in the list is the range [0, 5000].
  • -5000 <= Node.val <= 5000

Approach and Intuition

Overview

Given the mutable nature of linked lists, we aim to reverse the internal pointers of the list without changing the data values within each node:

  1. Initialize three pointers:
    • prev as None (since the new head's next should be None)
    • current as the head of the list (starting point)
    • next which will temporarily store the node next to current
  2. Iterate through the list:
    • Save the next node (i.e., current.next) into next
    • Reverse the current node's pointer (i.e., point current.next to prev)
    • Shift the prev and current pointers forward:
      • prev becomes current
      • current moves to next
  3. At the end of the iteration, prev will point to the new head of the reversed list.

Detailed Steps

  1. If the head is None or if there is only one node (head.next is None), return head as the list is already reversed in these cases.
  2. Utilize the three-pointer technique described above to systematically reverse the link directions from one node to the preceding node until reaching the end of the list.
  3. After traversing through all nodes, prev will point to the new head of the list since current will be None when the inputs are exhausted.
  4. Return the prev pointer, which now represents the head of the reversed list.

Examples Interpretation

  • Example 1: Reversing [1,2,3,4,5] must provide [5,4,3,2,1]. Starting with 1, we move each node to point to its predecessor until 5 becomes the first node.
  • Example 2: A simple case of two elements, [1,2] becomes [2,1] by swapping the connection between the nodes.
  • Example 3: An empty list simply returns an empty list, as there is nothing to reverse.

This systematic pointer adjustment method ensures that the link list is reversed in-place without utilizing additional storage, conformant with the constraints provided.

Solutions

  • C++
cpp
class Solution {
public:
    ListNode* reverse(ListNode* current) {
        if (current == nullptr || current->next == nullptr) {
            return current;
        }
        ListNode* reversedHead = reverse(current->next);
        current->next->next = current;
        current->next = nullptr;
        return reversedHead;
    }
};

The provided C++ code defines a solution to reverse a linked list using recursion. The function reverse takes a pointer to a ListNode as its parameter, which represents the current node of the linked list. This function implements the following logic:

  1. Base case: If the current node is nullptr or the next node of current is nullptr, the function returns the current node. This handles the cases where the list is empty or has just one node.
  2. Recursive step: The function recurses by calling reverse with the next node in the list.
  3. Reversal logic: Upon return from the recursive call, it sets the next pointer of the next node to point back to the current node, effectively reversing the direction of the link.
  4. Detachment: It then detaches the current node's next pointer by setting it to nullptr to ensure the previous start of the list now becomes the end.
  5. Completion: Once the entire list has been processed, reversedHead (which now points to the new head of the reversed list) is returned.

This recursive approach elegantly handles the reversal of a linked list by repositioning the links between nodes from the recursive call stack, ensuring that each node points to its predecessor, thus reversing the linked list.

  • Java
java
class Solution {
    public ListNode reverseLinkedList(ListNode start) {
        if (start == null || start.next == null) {
            return start;
        }
        ListNode newHead = reverseLinkedList(start.next);
        start.next.next = start;
        start.next = null;
        return newHead;
    }
}

This Java solution addresses the problem of reversing a linked list. The method reverseLinkedList employs a recursive approach to invert the order of nodes in the list. Initially, the method checks if the start node is null or a single node by evaluating if start.next is null, in which case it directly returns the start as reversing a single element or an empty list doesn't alter the list.

During each recursive call:

  • The function dives to the deepest node in the list using reverseLinkedList(start.next).
  • It sets the next node's next reference to point back to the current start node effectively reversing the link.
  • It then severs the original link by setting start.next to null.

Finally, the new head of the reversed list is returned upward through the recursion stack, culminating in the original call returning the new head of the completely reversed list. This tail-end method leverages the call stack to reverse the pointers efficiently without the need for auxiliary data structures.

  • Python
python
class Solution:
    def reverseLinkedList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
            
        newHead = self.reverseLinkedList(head.next)
        head.next.next = head
        head.next = None
        return newHead

The Python solution provided implements the reversal of a linked list using recursion. This method focuses on handling each node in the linked list, flipping its direction, and ensuring the list remains connected appropriately.

  • The function reverseLinkedList is a recursive function. It accepts a head which is the starting node of the linked list.
  • Check whether the head is null or it's the last node in the list (head.next is null). If true, return the head as it represents either an empty list or the last node which will become the new head of the reversed list.
  • Recursively call reverseLinkedList with the next node of the current head. This step continues until the base condition is met (reaching the end of the list).
  • Once reaching the end, reassign the next node's pointer, thus reversing the link. Specifically, head.next.next = head sets the next node's next pointer to the current node, effectively reversing the link.
  • Set head.next to None to break the original link and avoid cycles in the list.
  • Return newHead, the new head of the reversed list, which is obtained from the recursive calls reaching the base case.

This approach effectively reverses the linked list in-place without requiring additional data structures, relying on the call stack to handle the reversal as the recursion unwinds.

Comments

No comments yet.