Solution: Reverse Linked List

Let's solve the Reverse Linked List problem using the In-Place Manipulation of a Linked List pattern.

We'll cover the following

Statement

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

Constraints:

Let n be the number of nodes in a linked list.

  • 1≤1 \leq n ≤500\leq 500
  • −5000≤-5000 \leq Node.value ≤5000\leq 5000

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations, such as time complexity and any implementation constraints.

Naive approach

The naive approach to solve the reverse linked list problem is to create a new linked list by traversing the original linked list in reverse order. To do this, we can copy the nodes of the original linked list into another data structure, for example, a stack. Then, we can pop the nodes from the stack one by one, creating a new linked list with each node we pop.

This approach has a time complexity of O(n)O(n), since we need to iterate through the entire original list and then iterate through the stack. However, the space complexity is also O(n)O(n), since we need to store all the nodes in the data structure. This means that if the original linked list is very large, we may run into memory issues. Overall, while this approach is simple to implement, it may not be the most efficient solution for large linked lists.

Optimized approach using in-place manipulation of a linked list

The essence of this algorithm lies in its use of the in-place manipulation of an entire linked list without using extra memory. The algorithm reverses the linked list by traversing the list from the head to the tail while systematically reversing the direction of pointers between successive nodes. For each node, we point its next pointer to its previous node, effectively reversing the direction of the sublist up to that point. Before altering the next pointer of any node, we store its next node in a temporary pointer to avoid losing track of subsequent nodes. Finally, the head pointer is reassigned to the last node, marking the new head of the reversed list after the list has been fully reversed.

Now, let’s look at the workflow of the implementation of the algorithm.

  • Initialize three pointers: prev, next, and curr. The prev and next pointers are initialized as NULL, while the curr pointer is initialized to the head of the linked list.

  • Iterate over the linked list. While iterating, perform the following steps:

    • Before changing the next of curr, store the next node using the following line of code next = curr.next.
    • Now, we will update the next pointer of curr with the prev pointer. This will reverse the pointer of the current node from forward to backward, eventually aiding the reversal of the linked list.
    • After reversing the pointer, we’ll update prev as curr and curr as next using prev = curr and curr = next respectively.

  • After reversing the whole linked list, we’ll change the head pointer to the prev pointer because prev will be pointing to the new head node.

Let’s look at the following illustration to get a better understanding of reversing the linked list:

Press + to interact
canvasAnimation-image
1 of 12

Let’s implement the algorithm as discussed above:

main.java
LinkedListNode.java
LinkedList.java
PrintList.java
import java.util.*;
class ReverseLinkedList {
    public static LinkedListNode reverse(LinkedListNode head) {
        LinkedListNode prev = null;
        LinkedListNode next = null;
        LinkedListNode curr = head;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
        return head;
    }
    public static void main(String[] args) {
        int[][] input = {
            {1, 2, 3, 4, 5},
            {1, 2, 3, 4, 5, 6},
            {3, 2, 1},
            {10},
            {1, 2}
        };
        for (int i = 0; i < input.length; i++) {
			LinkedList<Integer> inputLinkedList = new LinkedList<Integer>();
            inputLinkedList.createLinkedList(input[i]);
            System.out.print((i + 1) + ".\tInput linked list: ");
            PrintList.printListWithForwardArrow(inputLinkedList.head);
            System.out.print("\n\tReversed linked list: ");
            PrintList.printListWithForwardArrow(reverse(inputLinkedList.head));
            System.out.println();
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Reverse Linked List

Solution summary

The solution summary is divided in the following parts:

  • Initialize three pointers: prev, next, and curr.
  • Reverse the links between adjacent nodes in a loop using the next, curr, and prev pointers.
  • After reversing the linked list, update the head pointer to the last node of the original linked list, which is now the first node of the reversed linked list.
  • Return the updated head pointer.

Time complexity

The time complexity of this solution is O(n)O(n), because we reversed the linked list in a single pass, where nn is the number of nodes in a linked list.

Space complexity

The space complexity of this solution is O(1)O(1), because no extra memory is used.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.