Reverse Linked List

1. Overview

In this article, we’re going to learn the different ways to reverse a linked list.

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.