# 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.

## Comments

## Post a Comment