**Difficulty:** Easy, **Asked-in:** Microsoft, Amazon, Adobe, SAP Labs, Qualcomm

- One of the popular linked list questions that can be solved using both iteration and recursion.
- A basic problem to improve understanding of pointer manipulation in a linked list. We can also solve many other coding questions based on this idea.

A head pointer of a linked list is given, write a program to reverse the linked list. We need to reverse the list by changing the links between nodes.

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

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

Input: 1->2->NULL

Output: 2->1->NULL

- Iterative approach using three-pointers
- Recursive approach using decrease and conquer

One idea for reversing a linked list is: Traverse the linked list using a loop and change the next pointer of each node so that it points to its previous node.

Linked list is a linear data structure where each node only points to its next node. So during this process, we should keep track of previous node using some pointer. Before changing the next pointer of the current node, we also need another pointer to track the next node.

Overall, we can use three-pointers for linked list reversal: One for tracking the current node, one for the previous node, and one for the next node. By the end of the loop, we return the new head reference.

- We initialize three-pointers
**prev**as NULL,**curr**as head and**forw**as NULL. -
We iterate through linked list until curr becomes NULL and keep changing each node's next pointer to its previous node. During this process, we update curr, prev, and forw pointers:

- Before changing the next pointer of curr node, we store the forw node i.e forw = curr->next.
- We change the next pointer of curr node and point it to prev i.e curr->next = prev.
- Now reversal of curr node is done. So we move prev and curr pointers one step forward i.e prev = curr, curr = forw

- Finally, by the end of loop, curr becomes NULL, and prev pointer is at the last node, which is the new head of linked list. So we return prev pointer as the new head reference.

Note: At each step of iteration, partially revered linked list size will grow by one.

```
class ListNode
{
int value
ListNode next
ListNode(int data)
{
value = data
next = NULL
}
}
ListNode reverseLinkedList(ListNode head)
{
if(head == NULL)
return NULL
ListNode curr = head
ListNode prev = NULL
ListNode forw = NULL
while (curr != NULL)
{
forw = curr->next
curr->next = prev
prev = curr
curr = forw
}
return prev
}
```

We are exploring each node and performing constant number of operations at each iteration. So time complexity = n*O(1) = O(1). We use constant extra space, so space complexity = O(1).

The critical question is: How can we solve this problem using recursion? In other words, how can we solve reversing a linked list problem using the solution of its smaller subproblems? Let's think.

Suppose the length of the linked list is n. The idea is to divide linked list into two parts: The head node and remaining linked list of size n - 1 (smaller sub-problem).

We recursively reverse the remaining linked list of size n - 1 by calling the same function with head->next as input parameter. This function will return head pointer of the reversed list of size n - 1 i.e. **restListHead = reverseLinkedList (head->next).**

After this partial reversal, head node will still point to the last node of the reversed list of size n - 1. In other words, next node of the head will be the last node of the reversed list of size n - 1. For the complete reversal, head should be the last node. So, we do the following operations to ensure this : head->next->next = head, head->next = NULL.

**Base case:** if (head == NULL || head->next == NULL), return NULL.

```
class ListNode
{
int value
ListNode next
ListNode(int data)
{
value = data
next = NULL
}
}
ListNode reverseLinkedList(ListNode head)
{
if (head == NULL || head->next == NULL)
return head
ListNode restListHead = reverseLinkedList(head->next)
head->next->next = head
head->next = NULL
return restListHead
}
```

We are recursively solving the problem of size n with a smaller sub-problem of size n - 1.

- Recurrence relation: T(n) = T(n - 1) + c
- The height of the recursion tree is O(n) because the input size is decreasing by 1. At each stage of recursion, we are doing constant operations. So, time complexity = O(n)
- Space complexity = O(n), for recursion stack space.
**(Think!)**

- Can we optimize the 1st approach and solve it using only two pointers?
- How can we reverse a linked list using stack?
- Why space complexity of the recursive solution is O(n)?
- How is the head getting fixed in the recursive method? Why don’t we use head->next = head to fix the head?

- Iterative approach: Time = O(n), Space = O(1)
- Recursive approach: Time = O(n), Space = O(n)

- Reverse a linked list from position M to N.
- Reverse a linked list in groups of a given size.
- Reverse a linked list using stack.
- Reverse a circular linked list.
- Reverse the first k elements of the given linked list.
- Reverse a doubly linked list.

**Enjoy learning, Enjoy algorithms!**

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.