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

Key takeaway: One of the basic linked list questions is to learn pointer manipulation and problem-solving using iteration and recursion. We can find many similar questions related to reversing various parts of the linked list.

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

- Reversing linked list iteratively
- Reversing linked list using recursion

One idea is to traverse the linked list using a loop and change the next pointer of each node so that it points to its previous node. During this process, we need to keep track of the previous node. On the other hand, before changing the next of the current node to the previous node, we also need to save the next node.

So, at each iteration, we partially grow the size of the reversed linked list by 1 and keep updating the nodes using three pointers: one for tracking the current node, one for the previous node, and one for the next node.

- We initialize three pointers:
**prev**as NULL,**curr**as the head, and**forw**as NULL. -
We iterate through the 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 the
**curr**node, we store the**forw**node, i.e.,**forw = curr->next**. - We change the next pointer of the
**curr**node and point it to**prev**, i.e.,**curr->next = prev**. - Now the reversal of the
**curr**node is done. So we move**prev**and**curr**pointers one step forward, i.e.,**prev = curr, curr = forw**.

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

```
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;
}
```

```
def reverseLinkedList(head):
if head is None:
return None
curr = head
prev = None
forw = None
while curr is not None:
forw = curr.next
curr.next = prev
prev = curr
curr = forw
return prev
```

```
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 explore each node and perform constant operations at each iteration. So, the time complexity = n*O(1) = O(1). We use constant extra space, so the space complexity is O(1).

The critical question is: 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. Now we divide the linked list into two parts: The head node and the 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 an input parameter. Now this will return the head pointer of the reversed list of size n - 1 i.e. **restListHead = reverseLinkedList (head->next).**

After this, the head node will still point to the last node of the reversed list of size n - 1. In other words, the next node of the head will be the last node of the reversed list of size n - 1. So for the complete reversal, the 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.

```
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;
}
```

```
def reverseLinkedList(head):
if head is None or head.next is None:
return head
restListHead = reverseLinkedList(head.next)
head.next.next = head
head.next = None
return restListHead
```

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

- 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!**

☆ 16-week live DSA course

☆ 16-week live ML course

☆ 10-week live DSA course

Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.

©2023 Code Algorithms Pvt. Ltd.

All rights reserved.