Invert Node Connections — Problem Statement & Solution Guide

MathEasyReverse Linked List

TimeO(n)

SpaceO(1)

Problem Description

You are given the head pointer of a singly linked list where each node contains an integer value and a reference to the next node. The task is to reverse the direction of the list in-place by reassigning the 'next' pointers of all nodes. After the operation, the original tail node becomes the new head, and the original head node becomes the new tail with its 'next' pointer set to null.

The reversal must be performed without creating new nodes or using additional data structures like stacks or arrays. You must manipulate the existing pointers directly to achieve the reversed sequence. Return the new head of the reversed list.

This operation effectively inverts the traversal order of the list. If the original list is 1 -> 2 -> 3, the resulting list should be 3 -> 2 -> 1, where the node containing 3 now points to 2, 2 points to 1, and 1 points to null.

DSA Pattern Breakdown

"Invert Node Connections"

easy

WHY DOES IT MATTER?

Reversing a linked list is a canonical example of in-place pointer manipulation, illustrating how to transform data structures without auxiliary storage. Mastery of this pattern demonstrates a candidate’s understanding of memory management, traversal techniques, and algorithmic efficiency, all of which are essential for systems that handle streaming data or require low-latency operations.

OPTIMIZATION CHALLENGE

The key insight is that each node’s 'next' pointer can be redirected in a single pass by maintaining a 'previous' pointer. This eliminates the need for auxiliary data structures and reduces the algorithm to O(1) space, which is critical for large-scale data streams.

REAL-WORLD CONNECTION

In distributed systems, reversing a linked list is analogous to reordering a chain of microservice calls or undoing a sequence of state changes. For example, a transaction rollback might need to traverse operations in reverse order to revert side effects, mirroring the pointer reversal logic.

When explaining this in an interview, emphasize the pointer update sequence: store the next node, reverse the link, then advance all pointers. Highlight that the algorithm’s correctness hinges on updating the pointers in the right order to avoid losing access to the remainder of the list.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

Reversing a singly linked list is a classic in-place algorithmic transformation that demonstrates pointer manipulation and iterative state maintenance. The naive approach—collecting all nodes into an auxiliary array or stack and then re-linking them—requires O(n) additional space and incurs overhead from dynamic memory allocation or recursion, making it unsuitable for very long lists or memory-constrained environments. The optimal paradigm uses three pointers—previous, current, and next—to traverse the list once, reassigning the 'next' reference of each node to its predecessor. This single-pass, constant-space method preserves the original list structure while achieving the desired reversal, and it scales linearly with the number of nodes, ensuring performance even for millions of elements.

The algorithm’s elegance lies in its simplicity: at each step, we detach the current node from the forward chain and attach it to the front of the reversed portion. By updating the pointers in a fixed order (store next, reverse link, advance pointers), we avoid losing access to the rest of the list. This pattern is a foundational building block for more complex operations such as cycle detection, list partitioning, and merging, making it a critical concept for both interview preparation and real-world codebases that manipulate linked data structures.

Interview Questions on This Problem

Q1What is the time and space complexity of reversing a singly linked list in-place, and why is it considered optimal?

The time complexity is O(n) because each node is visited exactly once, and the space complexity is O(1) because only a constant number of pointers are used regardless of list size. This is optimal because any algorithm must at least touch each node to reverse the links, and no additional storage beyond a few variables can be avoided.

Q2During an interview at a fintech platform, you’re asked to reverse a linked list that may contain duplicate values. How does the presence of duplicates affect your algorithm?

Duplicates do not affect the reversal logic; the algorithm operates purely on node references, not values. The only consideration is that the list’s integrity must be maintained, so the algorithm must still correctly update the 'next' pointers without assuming uniqueness.

Q3A high-growth startup asks you to reverse a linked list while also detecting if the list contains a cycle before performing the reversal. How would you approach this?

First, use Floyd’s Tortoise and Hare algorithm to detect a cycle in O(n) time and O(1) space. If a cycle is detected, you can either break the cycle by finding the loop’s entry point and setting its predecessor’s 'next' to null, or you can return an error. Once the list is confirmed acyclic, proceed with the standard in-place reversal.

Examples

Example 1

Input

head = [1, 2, 3, 4, 5]

Output

[5, 4, 3, 2, 1]

Explanation: Start with head=1. Reverse pointers: 5->4, 4->3, 3->2, 2->1, 1->null. New head is 5.

Example 2

Input

head = [10, 20, 30]

Output

[30, 20, 10]

Explanation: Original: 10->20->30. After reversal: 30->20->10->null. The node 30 becomes the head.

Example 3

Input

head = [7]

Output

[7]

Explanation: A single-node list remains unchanged. The head points to itself, and next is null.

Example 4

Input

head = [1, 1]

Output

[1, 1]

Explanation: Two nodes with identical values. The structure reverses, but the values appear the same. The second node becomes the head.

Constraints

The number of nodes in the list is in the range [0, 5000].
-5000 <= Node.val <= 5000
The list is guaranteed to be valid (no cycles).
The operation must be performed in O(n) time and O(1) space.

Optimal Approach & Strategy

Iterate through the list once, maintaining three pointers—previous, current, and next—to reverse each link in place. This uses only constant extra space and completes in a single traversal.

Brute Force Approach

Collect all nodes in an array or stack, then iterate over that collection to rebuild the list in reverse order, updating each node’s 'next' pointer. This requires O(n) extra space and two passes over the data.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
};

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

# Definition for singly-linked list.
# 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
        curr = head
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        return prev

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
};

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Invert Node Connections Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Math

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Invert Node Connections — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor