Command Palette

Search for a command to run...

Reverse Linked List

Problem Statement

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

You should reverse the list in-place without using extra space for another list.

Method Signature

Java
public static ListNode reverseList(ListNode head)

ListNode Definition

Java
class ListNode {
    int val;
    ListNode next;

    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Examples

Example 1:

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

Before: 1 -> 2 -> 3 -> 4 -> 5 -> null
After:  5 -> 4 -> 3 -> 2 -> 1 -> null

Example 2:

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

Before: 1 -> 2 -> null
After:  2 -> 1 -> null

Example 3:

Input: head = []
Output: []
Explanation: Empty list remains empty

Example 4:

Input: head = [1]
Output: [1]
Explanation: Single node list remains unchanged

Test Your Solution

Java
import java.util.ArrayList;
import java.util.List;

public class ReverseLinkedListTest {
    public static void main(String[] args) {
        // Helper method to create linked list from array
        ListNode createList(int[] values) {
            if (values.length == 0) return null;
            ListNode head = new ListNode(values[0]);
            ListNode current = head;
            for (int i = 1; i < values.length; i++) {
                current.next = new ListNode(values[i]);
                current = current.next;
            }
            return head;
        }

        // Helper method to convert linked list to array for easy checking
        List<Integer> listToArray(ListNode head) {
            List<Integer> result = new ArrayList<>();
            ListNode current = head;
            while (current != null) {
                result.add(current.val);
                current = current.next;
            }
            return result;
        }

        // Test case 1: [1,2,3,4,5]
        ListNode test1 = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result1 = reverseList(test1);
        System.out.println("Test 1: " + listToArray(result1)); // Expected: [5, 4, 3, 2, 1]

        // Test case 2: [1,2]
        ListNode test2 = createList(new int[]{1, 2});
        ListNode result2 = reverseList(test2);
        System.out.println("Test 2: " + listToArray(result2)); // Expected: [2, 1]

        // Test case 3: empty list
        ListNode test3 = null;
        ListNode result3 = reverseList(test3);
        System.out.println("Test 3: " + listToArray(result3)); // Expected: []

        // Test case 4: [1]
        ListNode test4 = createList(new int[]{1});
        ListNode result4 = reverseList(test4);
        System.out.println("Test 4: " + listToArray(result4)); // Expected: [1]

        // Test case 5: [1,2,3]
        ListNode test5 = createList(new int[]{1, 2, 3});
        ListNode result5 = reverseList(test5);
        System.out.println("Test 5: " + listToArray(result5)); // Expected: [3, 2, 1]
    }

    // Your implementation goes here
    public static ListNode reverseList(ListNode head) {
        // TODO: Implement linked list reversal
        return null;
    }
}

Extension Challenges

  1. Reverse in groups: Reverse nodes in groups of k (e.g., k=3)
  2. Reverse between positions: Reverse only nodes between positions m and n
  3. Palindrome check: Use reversal to check if list is palindromic
  4. Swap pairs: Swap every two adjacent nodes
  5. Rotate list: Rotate list to the right by k places

Real-World Applications

  • Undo operations: Reverse a sequence of operations
  • Browser history: Navigate backward through visited pages
  • Text processing: Reverse word order or character sequence
  • Game development: Reverse player movement history
  • Data structure implementation: Building other structures like stacks using reversed lists