# Coding Patterns: In-place Reversal of a Linked List

In Coding Patterns series, we will try to recognize common patterns underlying behind each algorithm question, using real examples from Leetcode.

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals and Cyclic Sort patterns and today, we will introduce In-place Reversal of a Linked List pattern which is very useful to solve the problems involving reversal of a Linked List with the constraint that we need to do it in-place without using extra memory.

LeetCode 206 - Reverse Linked List [easy]

Example:

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

### In-Place Reversal Solution

We are going to reverse one node at a time. We will start with a variable `current` which will initially point to the `head` of the Linked List and a variable `previous` which will point to the previous node that we have processed; initially `previous` will point to `null`.

We will reverse the `current` node by pointing it to the `previous` before moving on to the next node. Also, we will update the `previous` to always point to the previous node that we have processed.

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

class Solution:
def reverseList(self, head: ListNode) -> ListNode:

previous, current, next = None, head, None
while current is not None:
next = current.next  # temporarily store the next node
current.next = previous  # reverse the current node
previous = current  # point previous to the current node
current = next  # move on
return previous
``````

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

Space Complexity: O(1), algorithm runs in constant space.

## How to identify?

This approach is quite useful when dealing with reversal of Linked Lists when there is a constraint to do it without using extra memory.

When the problem gives this constraint and Linked Lists data structure, you should think about In-place Reversal of a Linked List pattern.

Tags:

Categories:

Updated: