#### Key takeaway

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

### Let’s understand the problem

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.

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

### Discussed solution approaches

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

### R﻿eversing linked list using iteration: Using three-pointers

#### Solution idea

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.

#### Solution steps

1. We initialize three-pointers prev as NULL, curr as head and forw as NULL.
2. 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
3. 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.

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

#### Solution pseudocode

``````ListNode reverseLinkedList(ListNode head)
{
return NULL
ListNode prev = NULL
ListNode forw = NULL
while (curr != NULL)
{
forw = curr->next
curr->next = prev
prev = curr
curr = forw
}
return prev
}``````

#### C++ implementation code

``````struct ListNode
{
int value;
ListNode* next;
ListNode(int data)
{
value = data;
next = nullptr;
}
};

{
return nullptr;
ListNode* prev = nullptr;
ListNode* forw = nullptr;
while (curr != nullptr)
{
forw = curr->next;
curr->next = prev;
prev = curr;
curr = forw;
}
return prev;
}``````

#### Python implementation code

``````class ListNode:
def __init__(self, x):
self.val = x
self.next = None

return None
prev = None
forw = None
while curr is not None:
forw = curr.next
curr.next = prev
prev = curr
curr = forw
return prev``````

#### Java implementation code

``````class ListNode
{
int val;
ListNode next;
ListNode(int x)
{
val = x;
next = null;
}
}

public class Solution
{
{
return null;
ListNode prev = null;
ListNode forw = null;
while (curr != null)
{
forw = curr.next;
curr.next = prev;
prev = curr;
curr = forw;
}

return prev;
}
}``````

#### Time and space complexity analysis

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

### R﻿eversing linked list using recursion: Decrease and conquer approach

#### Solution idea and steps

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.

#### Solution pseudocode

``````ListNode reverseLinkedList(ListNode head)
{
}``````

#### C++ implementation code

``````struct ListNode
{
int value;
ListNode* next;
ListNode(int data)
{
value = data;
next = nullptr;
}
};

{
}``````

#### Python implementation code

``````class ListNode:
def __init__(self, x):
self.val = x
self.next = None

#### Java implementation code

``````class ListNode
{
int val;
ListNode next;
ListNode(int x)
{
val = x;
next = null;
}
}

class Solution
{
{

}
}``````

#### Time and space complexity analysis

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

### Critical ideas to 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)?

### Comparison of time and space complexities

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

### Suggested problems to practice

• 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
☆ 10-Week Live DSA Course