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