Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Reverse a Linked List

Problem Statement

Write a Java program that reverses a singly linked list. The linked list consists of nodes, each containing an integer value and a reference to the next node. The program should reverse the order of the nodes (e.g., 1→2→3 becomes 3→2→1) using an iterative approach and print the reversed list. Test the implementation with linked lists of varying sizes, including empty lists, single-node lists, and multi-node lists. You can visualize this as rearranging a chain of numbered cards, flipping their order so the last card becomes the first.

Input:

  • A singly linked list of integers (e.g., 1→2→3→4). Output: The reversed linked list as a string (e.g., "4 3 2 1"). Constraints:
  • The list size is between 0 and 10^5.
  • Node values are integers in the range [-10^9, 10^9].
  • The list may be empty. Example:
  • Input: 1→2→3→4
  • Output: "4 3 2 1"
  • Explanation: The list 1→2→3→4 is reversed to 4→3→2→1.
  • Input: []
  • Output: "[]"
  • Explanation: An empty list remains empty.
  • Input: 5
  • Output: "5"
  • Explanation: A single-node list is unchanged.

Pseudocode

CLASS Node
    SET value to integer
    SET next to Node (null by default)
ENDCLASS

FUNCTION reverseList(head)
    SET prev to null
    SET current to head
    WHILE current is not null
        SET nextNode to current.next
        SET current.next to prev
        SET prev to current
        SET current to nextNode
    ENDWHILE
    RETURN prev
ENDFUNCTION

FUNCTION toString(head)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    WHILE current is not null
        APPEND current.value to result
        IF current.next is not null THEN
            APPEND " " to result
        ENDIF
        SET current to current.next
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of linked lists
    FOR each testCase in testCases
        PRINT test case details
        CALL reverseList(testCase.head)
        PRINT reversed list using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a Node class with: a. An integer value. b. A next pointer to the next node.
  2. In reverseList: a. Initialize prev as null, current as head. b. While current is not null:
    • Save current.next as nextNode.
    • Set current.next to prev (reverse the link).
    • Move prev to current, current to nextNode. c. Return prev as the new head.
  3. In toString: a. If head is null, return "[]". b. Traverse the list, append each value to a StringBuilder, add spaces between values. c. Return the string representation.
  4. In main, test with empty, single-node, and multi-node lists.

Java Implementation

public class ReverseLinkedList {
    // Node class for the linked list
    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    // Reverses the linked list
    public Node reverseList(Node head) {
        Node prev = null;
        Node current = head;

        while (current != null) {
            Node nextNode = current.next;
            current.next = prev;
            prev = current;
            current = nextNode;
        }

        return prev;
    }

    // Converts linked list to string for output
    public String toString(Node head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        Node current = head;
        while (current != null) {
            result.append(current.value);
            if (current.next != null) {
                result.append(" ");
            }
            current = current.next;
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        Node head;

        TestCase(int[] values) {
            if (values.length == 0) {
                head = null;
                return;
            }
            head = new Node(values[0]);
            Node current = head;
            for (int i = 1; i < values.length; i++) {
                current.next = new Node(values[i]);
                current = current.next;
            }
        }
    }

    // Main method to test linked list reversal
    public static void main(String[] args) {
        ReverseLinkedList reverser = new ReverseLinkedList();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{1, 2, 3, 4}), // Multi-node list
            new TestCase(new int[]{}),           // Empty list
            new TestCase(new int[]{5}),          // Single node
            new TestCase(new int[]{1, 1, 1}),    // List with duplicates
            new TestCase(new int[]{10, 20})      // Two nodes
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            TestCase test = testCases[i];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input list: " + reverser.toString(test.head));
            Node reversed = reverser.reverseList(test.head);
            System.out.println("Reversed list: " + reverser.toString(reversed) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input list: 1 2 3 4
Reversed list: 4 3 2 1

Test case 2:
Input list: []
Reversed list: []

Test case 3:
Input list: 5
Reversed list: 5

Test case 4:
Input list: 1 1 1
Reversed list: 1 1 1

Test case 5:
Input list: 10 20
Reversed list: 20 10

Explanation:

  • Test case 1: Reverses 1→2→3→4 to 4→3→2→1.
  • Test case 2: Empty list remains empty.
  • Test case 3: Single node 5 is unchanged.
  • Test case 4: List with duplicates 1→1→1 reverses to 1→1→1.
  • Test case 5: Two nodes 10→20 reverse to 20→10.

How It Works

  • Node: Stores an integer value and a reference to the next node.
  • reverseList:
    • Iteratively reverses links by adjusting next pointers.
    • Uses prev, current, and nextNode to track nodes.
    • Each step reverses one link, moving pointers forward.
  • toString: Converts the list to a space-separated string, returning "[]" for empty lists.
  • Example Trace (Test case 1):
    • Input: 1→2→3→4.
    • Initial: prev=null, current=1, nextNode=2.
    • Step 1: 1→null, prev=1, current=2, nextNode=3.
    • Step 2: 2→1→null, prev=2, current=3, nextNode=4.
    • Step 3: 3→2→1→null, prev=3, current=4, nextNode=null.
    • Step 4: 4→3→2→1→null, prev=4, current=null.
    • Return: 4→3→2→1.
  • Main Method: Tests multi-node, empty, single-node, duplicate, and two-node lists.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Reverse ListO(n)O(1)
To StringO(n)O(n)

Note:

  • n is the number of nodes in the list.
  • Time complexity: O(n) for reversing (single pass) and toString (traverse list).
  • Space complexity: O(1) for reversal (constant pointers); O(n) for toString (StringBuilder).
  • Worst case: O(n) time, O(n) space for large lists in output.

✅ Tip: Use an iterative approach to reverse a linked list to save space, adjusting pointers in a single pass. Test with empty and single-node lists to ensure edge cases are handled.

⚠ Warning: Be cautious when updating next pointers to avoid losing references to the rest of the list. Always save the next node before reversing the link.