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
Reverse a singly linked list.
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
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: 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.