Coding Patterns: In-place Reversal of a Linked List

3 minute read

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.

Problem: Reverse Linked List

LeetCode 206 - Reverse Linked List [easy]

Reverse a singly linked list.

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.

In-Place Reversal of a Linked List

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


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None:
            return head

        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.

Similar LeetCode Problems