Reverse Linked List - Java Solution

1. Introduction

This post will explore a common algorithmic challenge in linked list manipulation – reversing a singly linked list. Reversing a linked list is a fundamental problem in computer science and is often used as a stepping stone to understand more complex linked list operations.

Problem

The task is to reverse a singly linked list. Given the head of a linked list, we need to reverse the list such that the head points to the last node, and each node points to its previous node, eventually returning the new head of the reversed list.

2. Solution Steps

1. Initialize three pointers: prev (null initially), current (pointing to head), and next.

2. Iterate through the list. In each iteration:

a. Temporarily store the next node (next = current.next).

b. Reverse the current node’s pointer (current.next = prev).

c. Move prev and current one step forward (prev = current, current = next).

3. Continue this process until current becomes null.

4. At the end, prev will be pointing to the new head of the reversed list.

5. Return prev as the head of the reversed list.

3. Code Program

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class ReverseLinkedList {
    public static void main(String[] args) {
        // Example use case
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode result = reverseList(head);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }

    // Function to reverse a singly linked list
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        ListNode next = null;

        while (current != null) {
            next = current.next;    // Temporarily store the next node
            current.next = prev;    // Reverse the current node's pointer
            prev = current;         // Move prev one step forward
            current = next;         // Move current one step forward
        }

        return prev; // prev is now the new head
    }
}

Output:

5 4 3 2 1

Explanation:

1. reverseList: This function reverses a singly linked list.

2. It uses three pointers (prev, current, and next) to reverse the direction of the list. prev tracks the new list being formed, current tracks the current node in the original list, and next is used to temporarily store the next node.

3. In each iteration, the function reverses the next pointer of the current node and then moves both prev and current forward by one node.

4. The process continues until current reaches the end of the list (null).

5. At this point, prev points to the new head of the reversed list.

6. This approach efficiently reverses the list in place with O(1) extra space and O(n) time complexity.