 #### 2. Description

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

###### Example 1:

`Input: 1->2->3->4->5->NULL`

`Output: 5->4->3->2->1->NULL`

###### Example 2:

`Input: 1->2->NULL`

`Output: 2->1->NULL`

###### Example 3:

`Input: NULL`

`Output: NULL`

###### Constraints
• The number of nodes in the list is in the range [0, 5000].
• -5000 <= Node.val <= 5000

#### 3. Solution - Iterative Approach

The iterative approach uses two pointers to solve this problem. For this, we can use the In Place Reversal of a Linked List pattern that is useful for solving such problems with the constraint that is using the existing node objects without using extra memory.

##### 3.1 In-Place Reversal of a Linked List

In this pattern, we are going to reverse one node at a time. One variable `current` will point to the `head` of the linked list, and the second variable `previous` will point to `null`.

We will reverse the `current` variable by pointing it to the `previous` node before moving on to the next node. Then we’ll update the `previous` variable to always point to the `previous` node that we have processed. The loop will end when all nodes in the original list are reversed.

• Time complexity: O(N) where N is the number of nodes in the Linked Lists.

• Space complexity: O(1) since algorithm runs in constant space.

##### 3.2 How to identify
• This approach is quite useful when dealing with the reversal of Linked Lists when there is a constraint to use the existing node objects without using extra memory.

#### 4. Solution - Recursive Approach

The recursive approach is to do the reverse operation for `head.next`. Then we will set the `head.next.next` node to `head` and `head.next` node to `null`.

• Time complexity: O(N) where N is the number of nodes in the Linked Lists.

• Space complexity: O(N).

#### 5. Conclusion

In this tutorial, we looked into reversing a linked list using both iterative and recursive approaches.

Don’t just Leetcode, follow the Coding Patterns instead. Grokking The Coding Interview teaches you techniques and questions patterns to ace the coding interviews.

## Related Posts ### Merge Two Sorted Lists

1. Overview In this article, we’re going to learn the different ways to merge two sorted lists. 2. Description Given the heads of two sorted linked lists list1 and list2, merge the two lists into one sorted list. ### Build REST API with Spring Boot and Kotlin

1. Overview In this article, we’re going to build a REST API using Spring Boot 2.x and Kotlin. Meanwhile, dedicated support for Kotlin was introduced since Spring Framework 5. ### How To Create a Spring Boot Project

1. Overview In this tutorial, we’ll look into the different ways we can create a Spring Boot project. 2. Using Spring Initializer in spring.