While there are multiple ways to reverse a linked list, in this article, we are going to discuss an approach which traverses a linked list and reverse it in O(n) time complexity and O(1) space complexity.

Approach

There are five main steps to reverse a linked list in this approach. These are

Step 1: Initialize variables

We will need three variables to assist us in our problem. These will be

Current – Reference to the current node being processed.
Previous – Reference to the previous node of current node in the list.
Next – Reference to the next node of current node in the list.

Step 2: Change the next node reference of the current node

This is the step where the reversal takes place. We change the next node pointer of the current node to point to the previous node. Note that, with this step we don’t have a direct way to go to the next node and that’s where the next node variable comes handy.

Step 3: Set the previous variable to point to the current node

Before we move the current pointer to the next node, we have to move the previous node pointer to current node so that in the next iteration we can set the next node reference of current node to previous node variable and it points to the right node.

Step 4: Move current variable to point to next node

In this step, we set the current variable to point to the next variable node.

Step 5: Set next variable to point to the next node of current variable

We now move the next variable to the next node of current to have the reference to next node when reversal happens in step 2.

Implementation

Below is the code to reverse a linked list in Java.

package com.theaconitedev;

public class Main {

    private static class Node {
        public Node next;
        public int data;
    }

    public static void main(String[] args) {
        Node head = getList();
        printList(head);

        head = reverseList(head);
        printList(head);
    }

    private static Node getList() {
        Node head = null;
        Node current = null;

        for (int i = 1; i <= 5; i++) {
            Node newNode = new Node();
            newNode.data = i;

            if (i == 1) {
                head = newNode;
            } else {
                current.next = newNode;
            }

            current = newNode;
        }

        return head;
    }

    private static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }

        System.out.println();
    }

    private static Node reverseList(Node head) {
        Node previous = null;
        Node current = head;
        Node next = null;

        while (current != null) {
            next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }

        return previous;
    }
}

1 2 3 4 5 
5 4 3 2 1

TheAconiteDev

How to reverse a linked list?