Reverse a Singly Linked List - Java Solution

1. Introduction

In this blog post, we'll explore a fundamental problem in data structures: reversing a singly linked list using Java. Reversing a linked list is a common task in programming interviews and is pivotal in understanding linked list manipulation.

Problem

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

2. Solution Steps

1. Initialize three pointers: previous, current, and next.

2. Iterate through the list and, at each step, reverse the link between the current node and the next node.

3. Update the pointers appropriately to move through the list.

4. The reversal is complete when the current pointer reaches the end of the list.

5. Return the new head, which is the previous pointer at the end of the iteration.

3. Code Program

public class ListNode {
    int val; // Value of the node
    ListNode next; // Reference to the next node

    // Constructor to initialize the node with a value
    ListNode(int x) { val = x; }

    // Method to print the linked list starting from this node
    void printList() {
        ListNode temp = this;
        while(temp != null) {
            System.out.print(temp.val + " "); // Print the value of the current node
            temp = temp.next; // Move to the next node
        }
        System.out.println();
    }
}

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null; // Initially, 'prev' is set to null
        ListNode current = head; // 'current' starts from the head of the list
        ListNode next = null; // 'next' is used to temporarily store the next node

        // Iterate through the list
        while (current != null) {
            next = current.next; // Store the next node
            current.next = prev; // Reverse the link
            prev = current; // Move 'prev' forward
            current = next; // Move 'current' forward
        }

        // 'prev' is the new head of the reversed list
        return prev;
    }
}

// Example usage and testing
public class Main {
    public static void main(String[] args) {
        ListNode head = new ListNode(1); // First node of the list
        head.next = new ListNode(2); // Second node of the list
        head.next.next = new ListNode(3); // Third node of the list

        Solution solution = new Solution();
        ListNode reversedList = solution.reverseList(head);
        reversedList.printList(); // Print the reversed list
    }
}

Output:

3 2 1

Explanation:

The input list is 1 -> 2 -> 3. After reversing, the list becomes 3 -> 2 -> 1. 

The method reverseList changes the direction of each link in the list. 

Initially, each node points to its successor, but after reversal, each node points to its predecessor. 

The head of the reversed list is the last node of the original list.