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

**Example:**

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

Output:`[5, 4, 3, 2, 1]`

Your algorithm should run in **O(n)** time and use **O(1)** extra space.

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

A singly linked list represented by its head node.

The head of the reversed singly linked list.

- The number of nodes in the list is in the range
`[0, 5000]`

. `-5000 <= Node.val <= 5000`

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

The core challenge is to reverse the links between the nodes of the linked list. This problem is significant in many applications such as reversing data structures, undo operations, and more. A common pitfall is losing track of the next node when reversing the links, which can lead to a broken list.

To solve this problem, we need to reverse the direction of the links between the nodes. We can achieve this by iterating through the list and adjusting the pointers.

A naive approach might involve using additional space to store the nodes in a stack and then reconstructing the list. However, this would not meet the space complexity requirement of O(1).

The optimal solution involves using three pointers: `prev`

, `current`

, and `next`

. We iterate through the list, reversing the links as we go.

- Initialize three pointers:
`prev`

as`null`

,`current`

as`head`

, and`next`

as`null`

. - Iterate through the list:
- Store the next node in
`next`

. - Reverse the current node's pointer to point to
`prev`

. - Move
`prev`

and`current`

one step forward.

- Store the next node in
- Return
`prev`

as the new head of the reversed list.

Here is a step-by-step breakdown of the algorithm:

- Initialize
`prev`

to`null`

and`current`

to`head`

. - While
`current`

is not`null`

:- Store
`current.next`

in`next`

. - Set
`current.next`

to`prev`

. - Move
`prev`

to`current`

. - Move
`current`

to`next`

.

- Store
- Return
`prev`

as the new head of the reversed list.

```
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public class Solution {
public ListNode reverseList(ListNode head) {
// Initialize previous node as null
ListNode prev = null;
// Initialize current node as head
ListNode current = head;
// Iterate through the list
while (current != null) {
// Store the next node
ListNode next = current.next;
// Reverse the current node's pointer
current.next = prev;
// Move pointers one position ahead
prev = current;
current = next;
}
// Return the new head of the reversed list
return prev;
}
}
```

The time complexity of this algorithm is O(n) because we traverse the entire list once. The space complexity is O(1) because we only use a constant amount of extra space for the pointers.

Consider the following edge cases:

- An empty list (head is null): The function should return null.
- A list with a single node: The function should return the same node.

To test the solution comprehensively, consider the following test cases:

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

When approaching such problems, consider the following tips:

- Understand the structure of the data (linked list in this case).
- Visualize the problem with diagrams to understand the pointer movements.
- Break down the problem into smaller steps and solve each step iteratively.
- Practice similar problems to strengthen your understanding of linked lists and pointer manipulation.

Reversing a linked list is a fundamental problem that helps in understanding pointer manipulation and linked list operations. By practicing this problem, you can improve your problem-solving skills and gain a deeper understanding of linked lists.

For further reading and practice, consider the following resources: