Unfold Linked List Family Problems
Chapter 2: A Deeper Look Into Two Pointers Approach.
Table of Contents
Introduction
A group of friends decided to go to Vancouver Island on a camping trip. They were excited about this reunion because they were planning to arrange a small party for their recently married friends.
On the first weekend of July, they took a two hours flight from Edmonton to the Island. They arrived in the afternoon, and they checked in at one of the hotels that were close to the north side of the island, where the wildlife is. The next day, they drove to the north side of the island, carrying their camping stuff.
After they arrived at the camping location, some people were interested in starting hiking right away, and some people do not, because they wanted to eat something before going for a long walk. So, they had split into three groups, two groups were going hiking, and the other one was staying at the camp.
The first group started walking at 9 AM, and the other one at 11 AM. The two groups were walking into the forest, the view was breathtaking, and the weather was perfect, so everyone seem happy.
But, five hours later, the first group started to hear some voices ahead of them, so they walked towards the voice source… and, they were shocked!! They discovered that it was them, the second group. One of them said: “We must have walked in a circle, and got trapped in a maze”.
Now, the two groups started questioning how does that happen, and how they can get out of this maze.
One hour later, someone suggested a clever idea. The guy was a software engineer, so he suggested that they should call the third group to come and meet them at the maze entrance (point X). But, because it was too dark at the time, he was afraid they would get lost too and not notice the entrance. So, he asked the third group to stay on the phone while they are walking to the maze.
Also, he asked the third group to sync their walk together with them, step by step. So, every time the groups had a step, the third group also had a step.
But, after three hours, all the groups met exactly at point X at the same time, without any group missing it, hmm strange! How does that happen then? That is exactly what we are going to learn today!
In this post, we will dive deep into one of the most repetitive categories of questions in coding interviews. It is a brilliant algorithmic invention that has solved indexing problems when you have infinite collections. You will not find any application that runs in any operating system and does not use any of the concepts of this family. So, without further ado, let us welcome Linked List Family Problems.
Linked List Family is part of “A Deeper Look Into Two Pointers Approach” Chapter, where I discuss families of problems that are solved using the Two Pointers approach. My last post in this chapter addresses the KSum Family Problems, as the Two Pointers technique was used with the array data structure. This time, we will leverage two pointers technique to solve Linkedlist problems, which is highly likely your next interview question will be from it!
We will be discussing these problems:
Reverse Linked List
Linked List Cycle
Detect Linked List Cycle Start
Remove Nth Node From End of List
Swap Nodes in Pairs
Reverse Nodes in k-Group
So let us get started!
⚑ Reminder
What is a Linked List?
According to ChatGPT:
Linked List is data structure consisting of a sequence of nodes, where each node contains a value and a reference (or pointer) to the next node in the sequence.
Here is a visual illustration:
These are the main components that a Linked List consists of:
Head pointer: A variable that points to the first node in the list.
Node(s): A node that stores an object (number, ML model, …) which is usually called val, and a next pointer that points to the next node in the list.
3. Final Destination: This usually has a value equal to ‘NULL’.
Here is what a linked list node looks like in Python:
class Node:
def __init__(self, val, next_node):
self.val = val
self.next = next_nodeNow, let us get back to the problems!
1. Reverse Linked List
Reversing the nodes of a linked list is one of the important problems in this family. It opens the door to learning how to perform inplace manipulation of the nodes. As we will see later, the solution to this problem is used as a building block for other problems in this family.
1.1 Problem Description
In this problem:
Given the head of a linked list, reverse its nodes (inplace).
Inplace means: We should reverse the nodes inside the linked list, without using any extra memory space.
1.2 Example
Input: head
Output: [10, 8, 4, 5, 2]
1.3 Solution
To solve this problem, we will take the advantage of the KSum Family, where we introduced two pointers approach to solving array problems. Similarly, we will use the two-pointers approach here to reverse linked lists.
Suppose that we have a linked list that consists of two nodes:
Let’s define two pointers, prev and current. In the beginning, the prev pointer will point to NULL, whereas the current pointer will point to node(2). Let us see the figure below:
Now, to reverse this linked list:
First, we need to store the address of node(5) that follows node(2), because we don’t want to forget the anchor to the rest of the linked list nodes:
next_pointer = current_pointer.nextSecond, we need to change the pointer of node(2) to point to the previous node None, as follows:
current_pointer.next = prev_pointerThird, we must move prev to point to the node with the current pointer.
prev_pointer = current_pointerFinally, we set the current pointer to be equal to the next_pointer.
current_pointer = next_pointerLet’s see the complete flow of reversing all the nodes in the linked list:
Now, from the full code below, you can notice two things:
We will stop reversing the nodes of the linked list when the current pointer points to NULL.
Then, we will return the prev pointer, which will point to the reversed linked list.
| def reverse_list(head): | |
| if not head: return None | |
| prev_pointer = None | |
| current_pointer = head | |
| while current_pointer: | |
| next_pointer = current_pointer.next | |
| current_pointer.next = prev_pointer | |
| prev_pointer = current_pointer | |
| current_pointer = next_pointer | |
| return prev_pointer |
Time Complexity:
The time complexity of this solution will be:
Because we will be traversing all the nodes in the linked list.
Space Complexity:
Whereas, the space complexity will be:
with no extra memory space.
2. Linked List Cycle
Do you remember the story that I told you at the beginning of this post? Yes, the one about this group of friends? So, this is the problem that they have faced. As we will see in the next problem, how their software engineering friend has been able to rescue them from that maze!
2.1 Problem Description
In this problem, we are:
Given a head of a linked list that may have a cycle, we have to check if it contains a cycle or not.
2.2 Example
Input 1:
Output: True
Input 2:
Output: False
2.3 Solution
The solution to this problem is very intuitive to us. Imagine that you are passing through a street, and you suspect that you have visited this street before. The easiest way to know if this is true or false is by making a sign— let’s say — in one of the street buildings. Then if you see this sign again, you can confirm that you are stuck in a loop.
Similarly, to check if a linked list has a loop or not, we will use the Man-Sign analogy. The sign here will be a pointer called slow, and the walking man will be a pointer called fast. The fast-pointer will move with steps equal to twice the steps of the slow-pointer. Then, if there is a cycle, the fast-pointer will meet the slow-pointer in one of the nodes.
Here is a visual explanation of the proposed solution:
Here is the full code:
| def list_has_cycle(head): | |
| if not head: | |
| return False | |
| fast_p = head.next | |
| slow_p = head | |
| while fast_p: | |
| if slow_p == fast_p: | |
| return True | |
| fast_p = fast_p.next.next | |
| slow_p = slow_p.next | |
| return False |
Time Complexity:
The time complexity of this solution will be:
Because in the worst-case scenario, the cycle will be between the first and the last nodes.
Space Complexity:
The space complexity will be:
No extra space is used.
3. Detect Linked List Cycle Start
Now it is time to know how our software engineer rescued the group. The “Wow, you are a genius man” will be changed to “Aha! Yes, we know what he did”, so let’s unfold this mystery together.
In the last problem, we are asked to check if there is a cycle or not. Now, this time, we want to know where that cycle started. In other words, we should specify the exact place of where the loop started.
3.1 Problem Description
Given the head of a linked list, we have to detect the node in which that cycle started.
3.2 Example
Input 1:
Output: Node(4)
Input 2:
Output: Node(2)
3.3 Solution
Floyd’s Cycle detection algorithm is one of the well-known solutions that is invented to solve this problem. According to ChatGPT:
Floyd’s cycle detection algorithm, also known as the “tortoise and hare algorithm,” is an algorithm used to detect cycles in linked lists. The algorithm was proposed by Robert Floyd in 1960.
Floyd’s Cycle detection algorithm is composed of two connected sub-algorithms:
Cycle detection algorithm.
Cycle-start detection algorithm.
The idea of the Cycle detection algorithm is simple:
Initialize two pointers, a fast pointer that moves at a fast pace and a slow pointer that moves at a slow pace.
slow = head
fast = head2. Then at each step, the fast pointer will move two steps forward, and the slow pointer will move one step forward.
slow = slow.next
fast = fast.next.next3. Now if the two pointers meet at one of the nodes, then there is a cycle and if they do not meet, there is no cycle.
if slow == fast:
return slowThen, once we find there is a cycle, we pass the address of the node -where the two pointers meet q- to the Cycle start detection algorithm to locate the initial start of that cycle, as follows:
4. Initialize a pointer at the beginning of the linked list, and call it p.
p = head
q = meeting_point5. At each time step, move p and q one step.
while p != q:
p = p.next
q = q.next6. The meeting point of p and q represent the initial cycle start point.
Here is a visual illustration of this solution:
⚑ Note 1:
You may wonder why floyed’s detection algorithm work. Here is a good resource that explains the reason with a mathematical proof, so enjoy!
Now, let us see what the full code looks like:
| def get_pointers_meetingPoint(head): | |
| slow = head | |
| fast = head | |
| while fast and fast.next: | |
| slow = slow.next | |
| fast = fast.next.next | |
| if slow == fast: | |
| return slow | |
| return None | |
| def get_cycle_start(head, meeting_point): | |
| p = head | |
| q = meeting_point | |
| while p != q: | |
| p = p.next | |
| q = q.next | |
| return p | |
| if __name__ == '__main__': | |
| meeting_point = get_pointers_meetingPoint(head) | |
| if not meeting_point: | |
| return None | |
| else: | |
| return get_cycle_start(head, meeting_point) |
Time Complexity:
The time complexity of this solution will be:
Space Complexity:
The space complexity will be:
We have not used any extra memory space.
Break Time!
Now, IT IS TIME TO HAVE A BREAK! So please go and have some water, don’t get hydrated.
Welcome back! Now let’s jump to the last part of this long post!
4. Remove Nth Node From End of List
Now, let’s start this second part by jumping to another interesting problem where we have to delete a node from the end of a linked list.
4.1 Problem Description
Given the head of a linked list, and a number n that represents the index of the node that should be deleted from the end of the list. Remove the node, and return the head of the linked list.
4.2 Example
Input : [2,5,4,8,10], n=3
Output: [2,5,8,10]
4.3 Solution
To solve this problem, we will define two pointers, slow, and fast. Then, the idea is to make the distance between the two pointers equal to n. Here is what the steps look like:
Initialize two pointers slow, and fast that is pointing to the linked list head.
i_slow = head
j_fast = head2. Move the fast pointer n steps.
for _ in range(n):
j_fast = j_fast.next3. Then, move slow, and fast pointers one step at each time.
while j_fast.next:
j_fast = j_fast.next
i_slow = i_slow.next4. Then, if the fast pointer reaches the end of the list, where it points to nothing, Null, we remove the nₜₕ element as follows:
i_slow.next = i_slow.next.nextBecause the slow pointer at this time step will be right before the nₜₕ node ( nₜₕ -1).
Here is a visual explanation of the algorithm:
Let’s see the full code below:
| def remove_nth_node(head, n): | |
| i_slow = head | |
| j_fast = head | |
| # first we will move the fast pointer so that the distance between | |
| # j_fast - j_slow = n | |
| for _ in range(n): | |
| j_fast = j_fast.next | |
| if not j_fast: # return the next node to the slow pointer, if the | |
| # the number of nodes are less than n. | |
| return i_slow.next | |
| while j_fast.next: | |
| j_fast = j_fast.next | |
| i_slow = i_slow.next | |
| i_slow.next = i_slow.next.next | |
| return head |
Time Complexity:
The time complexity will be:
In the worst-case scenario, we must remove the node with n =1.
Space Complexity:
The space complexity will be:
no extra space is used.
5. Swap Nodes in Pairs
Here is one of the funniest problems in this family, and yet it is not an easy one, so be careful! Imagine that you are waiting in a line in one of Tim Horton's restaurants. This day, the restaurant has a special offer for customers who come for a pickup or dine-in.
So, they asked their customers who stand in the waiting line to change their places, in a way that any two neighbor customers should swap their locations. In exchange, any swapped pairs will get a free drink each.
Let’s see how that can apply to the linked list data structure.
5.1 Problem Description
So, let’s define the problem formally:
Given the head of a linked list, swap any adjacent node pair.
5.2 Example
Input 1
Output
Input 2
Output
5.3 Solution
To help our friends in the line to do the swapping, let’s take the previous example as follows:
To swap node(6) and node(3), we will:
Create a dummy node and set its next pointer to the head of the linked list.
Initialize three pointers prev_p, current_p, and next_p.
Set the prev_p pointer to point to the dummy node.
Set the current_p to point to node(6) (the linked list head).
Set the next_p pointer to point to node(3).
current_p.next = next_p.nextChange the current_p pointer to point to node(5).
current_p.next = next_p.nextChange the prev_p pointer to point to node(3).
prev_p.next = next_pSet the next pointer of the node that is pointed by the next_p pointer to point to node(3).
next_p.next = current_pMove the prev_p pointer to node(6)
prev_p = next_p.nextMove the current_p pointer to node(5)
current_p = current_p.next
Finally, move the next_p pointer to Null.
next_p = current_p.next
Now, let’s see the full code:
| def swap_node_pairs(head): | |
| if not head or not head.next: | |
| return head | |
| dummy_node = ListNode() | |
| dummy_node.next = head | |
| prev = dummy_node | |
| i = head | |
| j = head.next | |
| while prev.next and prev.next.next: | |
| # finish here | |
| j = i.next | |
| # code logically starts from here | |
| i.next = j.next | |
| j.next = i | |
| prev.next = j | |
| prev = j.next | |
| i = i.next | |
| return dummy_node.next |
Time Complexity:
The time complexity will be:
Space Complexity:
The space complexity will be:
Again, no extra space is used. Kudos to the Two Pointers technique!
6. Reverse Nodes in K-Group
This will be our last problem for this post, so I hope you that are enjoying this journey so far!
In our previous problem, when we reversed a linked list, we did that for all the nodes in the list. In this problem, we are interested in reversing each group that has K adjacent nodes.
6.1 Problem Description
Given the head of a linked list, and a number k that represents each group length, return the reversed K-Groups.
6.2 Example
Input
Output
6.3 Solution
Yes, I know what you are thinking of right now! Let me mimic what your brain is saying:
Hmmm, there is a reverse operation in this problem…. This problem is similar to the first problem in this post…hmmm, I think I can solve this problem… The only thing that I want is to specify the start, and the end of each group, then reverse it!
And I say a BIG YES! You are on the right track! Let me help you in developing this solution by taking the following example:
If each group length, K=3, here are the steps to reverse the linked list:
Initialize a dummy node that its next pointer points to the start of the linked list.
dummy_node = ListNode(val=0, next=head)2. Set prev_group_start_pointer to point to the dummy node. This pointer will serve as an anchor to the start of each group.
prev_group_start_pointer = dummy_node3. Get the end (end pointer ) of the first group (G₁={1,2,3}) by calling the move_pointer function where we pass prev_group_start_pointer as a start point.
end = move_pointer(prev_group_start_pointer, k)4. Set next_group_start_pointer to point to the first node in the next group.
next_group_start_pointer = end.next
5. Set a pointer (prev) to be equal to the next_group_start_pointer.
prev = next_group_start_pointer6. Set a pointer (current ) to be equal to the prev_group_start_pointer.
7. Reverse the group nodes by passing the prev, and current pointers to the reverse_list function.
prev, current = reverse_list( prev=prev, current=current,\\
next_group_pointer=next_group_start_pointer)8. Set a pointer (prev_group_end_pointer) to be equal to prev_group_start_pointer.next
prev_group_end_pointer = prev_group_start_pointer.next9. Update prev_group_start_pointer.next with the value of the end pointer.
prev_group_start_pointer.next = end10. Update prev_group_start_pointer with the value of the prev_group_end_pointer.
prev_group_start_pointer = prev_group_end_pointer11. Repeat steps 1–10 till the end pointer points to NULL.
if end == None:
break Here is a visual illustration that explains the previous steps:
See the full code below:
| def reverse_list(prev, current, next_group_pointer): | |
| while current != next_group_pointer: | |
| next_node = current.next | |
| current.next = prev | |
| prev = current | |
| current = next_node | |
| return prev, current | |
| def move_pointer(pointer, k): | |
| p = pointer | |
| while p and k > 0: | |
| p = p.next | |
| k -= 1 | |
| return p | |
| def reverse_nodes_Kgroups(head, k): | |
| dummy_node = ListNode(val=0, next=head) | |
| prev_group_start_pointer = dummy_node | |
| while True: | |
| end = move_pointer(prev_group_start_pointer, k) | |
| if end == None: | |
| break # end of the list | |
| next_group_start_pointer = end.next | |
| prev = next_group_start_pointer | |
| current = prev_group_start_pointer.next | |
| # pre_g-> o -> || o <- 1 <- 2 -> | 3 -> 4 -> 5 | |
| prev, current = reverse_list( | |
| prev=prev, current=current, next_group_pointer=next_group_start_pointer | |
| ) | |
| # store a pointer to the prev group. | |
| # pre_g-> o -> || 1 <- 2 -> | 3 -> 4 -> 5 | |
| prev_group_end_pointer = prev_group_start_pointer.next | |
| # glue the two groups. | |
| # pre_g-> o -> || 2 -> 1 -> 3 -> 4 -> 5 | |
| prev_group_start_pointer.next = end | |
| # store the prev node. | |
| # 2 -> 1 -> |pre_g->|3 -> 4 -> 5 | |
| prev_group_start_pointer = prev_group_end_pointer | |
| return dummy_node.next | |
| # call the reverse function. | |
| reverse_nodes_Kgroups(head, k) |
Time Complexity:
The time complexity will be:
Space Complexity:
While the space complexity will be:
Because there is no extra space used!
7. Family Patterns
As we can see clearly from the problems in this family, they all use the Two Pointers Approach. Some problem solutions use just two pointers, and others use more than two pointers, such as Reverse Nodes in K-Groups.
However, here is a summarization of the Two Pointers approach for the Linked List Family Problems that we have encountered in this post:
1. Dummy Node
When you encounter a linked list problem or problem that has an infinite collection, think about if adding a dummy node at the start of the linked list could help solve your desired problem.
2. Current & Prev Pointers
Start always by defining current and prev pointers as shown in the figure above. The node where the current pointer is where the modification or change should happen, and the node with the prev pointer is usually where the information that is needed for the current update exists.
3. Stop Point
Pay attention to where and when your linked list traversal should stop. Should it stop when it points to the Null, the last node, the pre-last node…etc?
8. Recap
In this post, we have covered part 1 of the Linked list Family problems. This Family is part of the Two Pointers Approach Chapter, where we discuss a series of families that use Two Pointers as the main approach to solving their problems!
To summarize this post, here are the main points:
Floyd’s cycle detection algorithm is an algorithm used to find cycles in linked lists.
Floyd’s cycle detection algorithm can help you to detect a cycle and its start point.
Initializing dummy nodes is important when you deal with linked list problems, as they work as an anchor to your list, especially when you have an inplace operation.
Linked List traversal needs you first to specify when to stop, which sometimes could be tricky and challenging. ( having more than two pointers moving at the same time)
9. Next Post
In the next post, we will dive deep into more Linked list inplace problems where the change should happen inside the linked list without using any extra space, so let’s see how we can get the most out of the Two Pointers approach to solve these problems. So, STAY TUNED!
New to this series?
New to the “Unfold Algorithm Coding Interviews For Data Scientists” series? Start from the beginning, here [link to the series list]
Any oversights in this post?
Please report them through this Feedback Form, I really appreciate that!
Thank you for your reading!
You can learn more about the date of future posts for this series through my newsletter, where I talk about Algorithms, Machine Learning, and Data Science.
If you have any other questions or comments, please do not hesitate to share them with me through Newsletter | Medium | LinkedIn | Twitter. See you soon!
Resources
[1] Vivekanand Khyade — Algorithm Every Day, Why Floyd’s cycle detection algorithm works? Detecting loop in a linked list, 2018, Youtube.com.
[2] Reverse Linked List, LeetCode, LeetCode.com.
[3] Linked List Cycle, LeetCode, LeetCode.com.
[4] Linked List Cycle II, LeetCode, LeetCode.com
[5] Remove nth node from end of list, LeetCode, LeetCode.com.
[6] Swap nodes in pairs, LeetCode, LeetCode.com.
[7] Reverse Nodes in k-Group, LeetCode, LeetCode.com