To watch the youtube video going over this topic, click here.
Introduction
Linked Lists are a fundamental data structure, and they're often asked about in interview questions. Being able to work with multiple levels of a linked list teaches you how to work with all categories of linked list problems.
In this blogpost we'll go through three layers of reversing a linked list, all of which increase in difficulty, but are related to the same base algorithm. (All of these questions are problems on Leetcode.) The problems we'll review are:
[Easy] Reverse A Linked List
Given the head of a singly linked list, reverse it. (Leetcode Problem.)
Solution (Iterative Approach)
We want to iterate through the linked list and change each node's next pointer to point to the previous node in the list.
To do this, we need too maintain two extra pointers while traversing the list, one that points to the previous node and one that points to the current node we're updating. Here's some C++ Code that does the iterative approach.
The time complexity is O(N) because we visit each node in the list once.
The space complexity is O(1) because the only extra data we have is three pointers. [Medium] Reverse A Linked List From Node m to Node n
Given the head of a singly linked list, reverse nodes m to n. (Problem on Leetcode.)
Solution (Iterative Approach)
The "reversing" part is going to be the same algorithm as the base problem. The difference is, this time we have to start/stop reversing at specific nodes, and we're left with some disconnected sublists that we need to rejoin. To do this, we just need to maintain two extra pointers, one pointer to the node before the reversed chain, and one pointer to the end of the reversed chain.
The algorithm is as follows:
Here's a diagram of that algorithm in action:
Here's C++ code that implements this algorithm:
The time complexity is O(N) because we visit each node in the list once.
The space complexity is O(1) because the only extra data we have is three pointers. [Hard] Reverse A Linked List In k Groups
Given the head of a singly linked list, reverse groups of knodes at a time. If there aren't k nodes left for a group, then don't reverse them. (Problem on Leetcode.)
Solution (Iterative)
The solution to this problem builds on the previous two problems: we still use the "change next pointer to point to the previous node" reverse technique from the easy problem, and we still worry about reconnecting chains after the reversal, like the medium problem.
The difference is, this time we'll continuously reverse, starting from the head of the linked list, until we run out of klength chains to reverse. The one thing we have to keep in mind is updating the prev pointer after each reversal chain.
Here's C++ code that implements the algorithm:
The time complexity is O(N) because we visit each node in the list twice.
The space complexity is O(1) because the only extra data we have is a few pointers and integers. Alternative Solutions
We should make note that the way we solved these problems were all through an iterative algorithm. There are three other types of algorithms possible, but they're all not ideal:
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake Priority Queues
Priority queues are a special data structure. They're backed by heaps (a type of binary tree), but are used like queues.
What makes a priority queue better than an ordinary queue is that the priority queue will maintain sorted order in O(logN) time even while inserting or removing new elements. The easiest way to use a priority queue is with primitive data types, such as integers and strings. However, it's possible to use priority queues on custom types, or to be able to write a custom sorting order for primitive types. Custom Comparators
Just like with sorting vectors, it's possible to use a custom comparator with priority queues, which defines how elements in the priority queue are ordered. Traditionally in C++ this is done using a struct, but lambda expressions are quicker to write and also offer the benefit of being able to reference variables outside of its scope (which is tricky to do with structs).
Here's some C++ code that uses a priority queue with a custom comparator, and the custom comparator (which is a lambda expression) is even able to make use of a hash map outside of its scope for its comparisons.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake
To watch the youtube video going over this topic, please click here.
Problem Statement
A matrix (2D array) has cells that are filled with one of three possible values:
Given a matrix, to return the number of turns it takes until there are no humans left. (And if any human survives, then return 1.) ("Rotting Oranges" problem on Leetcode.) Solution (Multiple BFS)
Theory
The way we'll solve this problem is by updating the matrix each turn by infecting humans next to any zombies. However, there are two things we need to watch out for:
With this in mind, we'll use a queue to hold each zombie, and for each zombie in the queue we'll process it by allowing it to infect any humans adjacent too it (meaning pushing that newly created zombie onto the queue to be processed later). However, the part where our code is going to become easier to read (and differs from the Leetcode solution) is that each Zombie in our queue will store their matrix position (i,j) and the turn it got infected. To do this, we'll have a special data structure (a struct or a class) to store this extra info.
Algorithm
C++ Code
Analysis The time complexity is O(N), where N is the number of cells in the matrix, since we'll process each cell at most once. The space complexity is O(N), since at worst the queue holds all zombies. (Meaning we start out with a matrix full of zombies and they all get pushed into the queue.) Note: This solution is called "multiple BFS" because we're using a queue to traverse nodes (zombies) like the BFS algorithm, but we've got multiple nodes (zombies) being traversed at the same time.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake 
AuthorHi, I'm srcmake. I play video games and develop software. Protip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.
