Start learning free

LESSON 297 OF 410 · LINKED LISTS

Reverse Linked List in O(n) Time and O(1) Space using Java

Practice O(n) Read the full explanation

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

Example:

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


Note:

Your algorithm should run in O(n) time and use O(1) extra space.


Hints:

This problem is very similar to "Reverse String" problem, so it's natural to think of adapting that solution for Linked Lists. Unfortunately, traversing with two pointers doesn't work here because the right pointer should move to the left, and we cannot do that in a Linked List. The trick is actually in modifying the links of our Linked List to obtain its reversed version. How should we modify them?

We just have to reverse each link in the list. For example: 1 -> 2 -> 3 -> 4 should become 1 <- 2 <- 3 <- 4. And the head of the reversed list is the tail of the original one. How can we reverse these links?

One idea is to traverse the list from left to right using a variable node and convert each link node -> node.next to node.next -> node. In plain steps: start with node at the head; while node is not null, set nextNode to the node after node, make that next node point back at node, then move node forward to nextNode. But there is a problem with this algorithm. Can you find out what that is? Take some small example and run it by hand.

The problem is that the moment we reverse a link, we lose access to the next nodes. For example, if the list is 1 -> 2 -> 3. When node is 1, we reverse the link and the list becomes 1 <- 2 3. We lost the link between 2 and 3. And so at the next step node becomes 2 but node.next is 1 instead of 3. The solution is still good, but we need to implement it in such a way that this problem is fixed.

We should traverse the linked list, while using two pointers:
  • prev - the previous node
  • node - the current node
We will start with the first two nodes in the list: prev is the head and node is the node after the head. Then, for as long as node is not null, we will reverse the link prev -> node and update the two variables such that they point to the next two nodes. Can you figure out how to code this? Take the example above and figure out how you should update the pointers after each link reversal.

Start with prev at the head and node at the node after it. While node is not null:
  • save the node after node in nextNode;
  • make node point back at prev;
  • move prev to node;
  • move node to nextNode.
Don't forget to cut the old head's link to the second node, so the reversed list ends there, and return the new head.

STEP 1 OF 9
    Ctrl + Enter to check

    JAVA · LINKED LISTS

    Reverse Linked List in Java, explained

    Problem Definition

    The task is to reverse a singly linked list. Given the head of the list, we need to reverse the list and return the new head of the reversed list.

    Input:

    A singly linked list represented by its head node.

    Output:

    The head of the reversed singly linked list.

    Constraints:

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

    Example:

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

    Understanding the Problem

    The core challenge is to reverse the links between the nodes of the linked list. This problem is significant in many applications such as reversing data structures, undo operations, and more. A common pitfall is losing track of the next node when reversing the links, which can lead to a broken list.

    Approach

    To solve this problem, we need to reverse the direction of the links between the nodes. We can achieve this by iterating through the list and adjusting the pointers.

    Naive Solution

    A naive approach might involve using additional space to store the nodes in a stack and then reconstructing the list. However, this would not meet the space complexity requirement of O(1).

    Optimized Solution

    The optimal solution involves using three pointers: prev, current, and next. We iterate through the list, reversing the links as we go.

    Steps:

    1. Initialize three pointers: prev as null, current as head, and next as null.
    2. Iterate through the list:
      • Store the next node in next.
      • Reverse the current node's pointer to point to prev.
      • Move prev and current one step forward.
    3. Return prev as the new head of the reversed list.

    Algorithm

    Here is a step-by-step breakdown of the algorithm:

    1. Initialize prev to null and current to head.
    2. While current is not null:
      • Store current.next in next.
      • Set current.next to prev.
      • Move prev to current.
      • Move current to next.
    3. Return prev as the new head of the reversed list.

    Code Implementation

    /**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        // Initialize previous node as null
        ListNode prev = null;
        // Initialize current node as head
        ListNode current = head;
        
        // Iterate through the list
        while (current != null) {
            // Store the next node
            ListNode next = current.next;
            // Reverse the current node's pointer
            current.next = prev;
            // Move pointers one position ahead
            prev = current;
            current = next;
        }
        
        // Return the new head of the reversed list
        return prev;
    }
}

    Complexity Analysis

    The time complexity of this algorithm is O(n) because we traverse the entire list once. The space complexity is O(1) because we only use a constant amount of extra space for the pointers.

    Edge Cases

    Consider the following edge cases:

    • An empty list (head is null): The function should return null.
    • A list with a single node: The function should return the same node.

    Testing

    To test the solution comprehensively, consider the following test cases:

    1. Input: head = []
   Output: []

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

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

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

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Understand the structure of the data (linked list in this case).
    • Visualize the problem with diagrams to understand the pointer movements.
    • Break down the problem into smaller steps and solve each step iteratively.
    • Practice similar problems to strengthen your understanding of linked lists and pointer manipulation.

    Conclusion

    Reversing a linked list is a fundamental problem that helps in understanding pointer manipulation and linked list operations. By practicing this problem, you can improve your problem-solving skills and gain a deeper understanding of linked lists.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free