Master Linked Lists for
Coding Interviews: 8 Must-Solve LeetCode Problems
⏱️ Estimated reading time: 16
minutes
When you think about how
software engineers work with data, they will tell you that data rarely behaves
in an organized pattern (like a neat row of boxes); instead, data tends to
grow, shrink, move around, and be very demanding regarding its flexibility. Linked
lists were designed to solve this problem. A linked list is a linear data
structure in which each piece of information called a node has two parts:
1) The piece of
information that you want to store and
2) The address or
reference to the address of the next node in the list so that the first and
second nodes are linked together.
Linked lists do not store
the nodes in contiguous memory, thus eliminating time-consuming processes
because insertion or deletion of nodes does not consist of shifting large
numbers of nodes. Because linked lists are dynamic by nature, linked lists are
used extensively within the industry for building systems like stacks, queues,
memory management, file systems, and hash table chaining, where data will
frequently change or require dynamic allocation. Essentially, linked lists
offer a trade-off between direct indexing speed and flexibility, thus being a
very powerful tool for designing systems in the real world.
🟢 EASY (Foundational
+ Pattern Building)
I.
Reverse Linked List
🧠 Explanation
With this solution, a
singly linked list can be reversed using an iterative approach that involves
manipulating the pointers instead of creating a new list. Essentially, each
node in a linked list has a next pointer that is currently directing other nodes
forward through the linked list, this solution will reverse that direction by
changing the point of the next pointers to all point back to their preceding
node.
The algorithm being
implemented will maintain two pointers, curr, the current node being processed,
and prev, the preceding node. The prev pointer is initially set to None;
therefore, when the new head of the reversed linked list is completed, the next
pointer will point to None. For every iteration, the direction of each node's
next pointer will be redirected back to the preceding node, thereby reversing
the direction of all the linked list's nodes. Once all of the linked list's
nodes have been processed, the pointers will grow until they point beyond all
processed nodes, therefore reaching the end of the linked list. At the end of
the processing of the nodes, the prev pointer will be pointing to the new head
of the reversed linked list; this will therefore be returned as the final
result.
⚙️ Logic in Steps
1.
On this occasion, the process involves 2
pointers: prev = NULL, curr = head.
2.
While traversing through the linked list
until curr is NULL,
i)
Store the next node in "nxt =
curr.next" to ensure you do not lose sight of them,
ii)
ii) Reverse the link so that
"curr.nxt = prev",
iii)
iii) Update the prev pointer to the
current node,
iv)
iv) Move the curr pointer to the next node
(as saved in step 1).
3.
Keep repeating until all nodes have been
reversed.
4.
Return prev as the new head of the
reversed list.
⏱ Time and Space Complexity
Time Complexity O(n):
Traversing the entire
linked list once
Space Complexity O(1):
No additional data
structures are used; only a few pointers are maintained.
📝 Key Takeaways from This Problem
and Solution
1.
Reversing a linked list can be considered
one of the most commonly performed pointer manipulation operations.
2.
This algorithm is able to perform the
reversal in a memory efficient manner because it is performed in-place.
3.
By saving the next node of each node prior
to reversing the pointer to that next node, and from that point onward, you
will not lose access to any of the remaining linked list.
4.
This technique of reversing a linked list
is commonly used for transforming linked lists, as well as for various
interview problems, and in low-level (i.e., system) programs where memory
efficiency is important.
II.
Merge Two Sorted Lists
🧠 Explanation
A solution exists for
joining two ordered linked lists together into a single ordered linked list.
Instead of generating new nodes, it reuses the original nodes and connects them
in a sorted way. A temporary node is utilized as the first node in the
newly-built list to make construction easy. A tail pointer is also maintained
to track where the last node is located in the combined list. The algorithm
compares each current node between both lists then adds the lowest valued node
to the merged list, advancing the pointer for that respective list.
As long as there are
nodes left in both linked lists, the process will repeat until one of them has
no nodes left. At this point, any remaining nodes from the list with nodes left
will simply be added to the merged list. After the end of this process, dummy.next
will be returned as the head of the new ordered linked list created by merging
the original two ordered linked lists together to make one complete list.
⚙️ Logic in Steps
1.
To create a dummy node as your merged
list's initial reference.
2.
To create a pointer tail to build the
merged list.
3.
While both list1 and list2 are not empty,
iterate through both lists.
4.
Compare the values min(list1.val,
list2.val).
5.
Append the shorter of the two nodes to
tail's next.
6.
For the node you just appended, move the
pointer for that list (list1 or list2).
7.
Move the tail pointer to the last node you
appended.
8.
Once one of the lists is empty , append
the remaining nodes from the other list.
9.
Return dummy.next as the head of the
merged list.
⏱ Time and Space Complexity
Time Complexity O(m+n)
Each node from both lists
is visited exactly once
Space Complexity O(1)
No extra data structures
are used; nodes are reused from the original lists.
📝 Key Takeaways from This Problem
and Solution
1.
Using a dummy node simplifies linked list
construction and avoids edge cases.
2.
Since both lists are already sorted, a
two-pointer comparison strategy efficiently merges them.
3.
Reusing nodes instead of creating new ones
keeps the algorithm memory efficient.
4.
This merging technique is widely used in
algorithms like Merge Sort and data stream merging in real-world systems.
III.
Linked List Cycle
🧠 Explanation
This algorithm determines
whether or not a cycle (loop) exists within a linked list using the Tortoise
and Hare algorithm, or Floyd's Cycle Detection Algorithm. Two pointers are
used, slow and fast; the slow pointer advances by one step and the fast pointer
advances by two steps. If a cycle exists in the linked list, the fast pointer
will eventually meet up with the slow pointer. At this point, both of the pointers
will be at the same node in the linked list, which will be inside of the cycle
(loop). When there is NO cycle in the linked list, the fast pointer will
eventually reach the end of the linked list (None). In this case, it will
conclude that there is no cycle and return False.
⚙️ Logic in Steps
1.
If the list doesn't have any nodes or if
it has only 1 node, return false because there can't be a cycle.
2.
In the same manner, use pointers to
traverse the list and set one pointer at the head of the list, slow = head; and
set another pointer at the head of the list, fast = head.
3.
Begin traversing the linked list while the
pointer of fast and the pointer of fast.next are not equal to null (executing
as a loop).
4.
For each iteration through the above loop,
increment the slow pointer by 1 (slow = slow.next) and increment the fast
pointer by 2 (fast = fast.next.next).
5.
For each time that you increment either
the slow pointer or the fast pointer, check if the slow pointer equals the fast
pointer; if the pointers are the same, then a cycle exists, and return true.
6.
If the loop completes and the two pointers
do not meet, return false.
⏱ Time and Space Complexity
Time Complexity O(n):
Each pointer traverses
the linked list at most once
Space Complexity O(1):
The algorithm uses only
two pointers and no additional data structures.
📝 Key Takeaways from This Problem
and Solution
1.
When it comes to identifying cycles in
linked lists, Floyd's algorithm (also referred to as "the tortoise and
hare") is regarded as one of the most effective techniques available.
2.
Floyd's algorithm involves the use of two
pointers moving at different speeds, allowing for detection without requiring
any additional memory.
3.
Many commonly used techniques now existed
for detecting loops are now incorporated into such memory management systems
and will serve to help you with application of graphs through graph rotation
and then transferring this technique to any number of applications.
IV.
Remove Linked List Elements
🧠 Explanation
This algorithm will
delete any nodes from a given singly linked list whose data match the supplied
value val. The simplest method of omitting the head node that satisfies this
criterion, is to create a new dummy head node that points to the original head
node of the list. In the algorithm, a pointer curr starts as the dummy node and
traverses the entire list. At each node, curr checks the value of curr.next. If
the value is equal to val, this indicates that this node is to be removed and
the link to it will be skipped by performing curr.next = curr.next.next.
Otherwise, curr will simply continue traversing the linked list one node
forward.
By reconstructing the
links, rather than creating a new linked list, we can perform the task of
removing the undesired nodes from the already existing linked list; and
therefore, all remaining nodes will stay in their original positions. After all
nodes have been processed, the algorithm returns dummy.next, which represents
the new linked list head node.
⚙️ Logic in Steps
1.
Make a temp point to the Head of the
linked list
2.
Make a curr pointer, point to the Dummy
3.
While curr.next is not null, repeat
process
4.
Check if curr.next will equal val
5.
If it is equal to the val, delete node by
making curr.next = curr.next.next
6.
If it is not equal to, move and make curr
= curr.next
7.
Repeat until curr is null.
8.
Return the temp as a new head of the
linked list.
⏱ Time and Space Complexity
Time Complexity O(n):
Each node in the linked
list is visited once
Space Complexity O(1):
No additional data
structures are used, and the list is modified in-place.
📝 Key Takeaways from This Problem
and Solution
1.
A dummy node assists in handling edge cases such as deleting the first node in a linked list.
2.
When removing a node from a linked list, we do not need to shift the nodes; instead, we only need to change pointers.
3.
The algorithm processes the data in one go which makes the algorithm very efficient.
4.
This is a common technique to filter data,
where specific elements of the data need to be removed from streams, the linked
list is modified in place.
🟡 Medium (Interview-Level
Skills)
V.
Add Two Numbers
🧠 Explanation
This code is going to be
used to add two given numbers, which are expressed as linked lists. Each
element in the linked list will contain a single digit. The two linked lists
will then each present their numbers in reverse order, and we will return the sum
of these two linked lists as a linked list in reverse order. The algorithm
performs the same steps manually that one would take to add numbers together
using basic addition algorithms in elementary school. It will iterate through
each of the two input linked lists, add each digit of the two numbers together
(including the carry from the previous step, if applicable), and store the
result digit into the appropriate position of a newly created linked list.
Again; a dummy node is
used for ease of list creation, and curr will represent a pointer to build the
newly created sum list. At each step we will calculate both the sum of the two
input linked list digits and the carry from the previous iteration. The last
digit of the summed result will become the stored digit of the new node, while
the remaining digit from that summed result will be considered the carry for
the next step in this iteration. This loop continues until both input linked
lists have been completely evaluated and any remaining carry has been added to
a new node. The result of this process will give us the head value associated
with the newly created sum linked list, which will begin with dummyNode.next
(which will also equal NULL if both lists were empty or if both lists were made
up of all zero values).
⚙️ Logic in Steps
1.
Create an initial dummy node for your
results.
2.
Then create a variable called curr to use
while building the results and carry = 0 to help with calculations.
3.
Now you’ll want to create a while loop
that will loop through both linked lists l1 and l2 as long as they’re both
still there and the carry has a value greater than 0.
4.
For both l1 and l2 retrieve the values
contained in both nodes (use 0’s for any additional values). Calculate a total
equal to the sum of the values of the current nodes from your linked lists plus
the carry.
5.
Now, calculate a new value for your carry
using the following - carry = total // 10.
6.
Now, create a new node based on the total
% 10 (using this value) and append it to your result. Then, use the curr
variable to increment the value of curr.
7.
If either l1 or l2 point to a node that
exists, move the pointers to that node.
8.
Once the loop has gone through all of the
values, return dummy.next to get your resulting linked list.
⏱ Time and Space Complexity O(max(n, m))
Time Complexity
Each node from both
linked lists is processed once
Space Complexity O(max(n,
m))
A new linked list is
created to store the result.
📝 Key Takeaways from This Problem
and Solution
1.
The method for performing the addition
algorithm follows the same step by step method of adding the digits of a number
that we use in math.
2.
Using a temporary ("dummy") node
can help to make it easier to build linked lists.
3.
When adding two numbers, the carry
variable makes it possible to add sums which exceed 9.
4.
This method of adding large numbers is
also frequently used in financial systems, large integer arithmetic, and
numeric calculations where the resulting numbers exceed the data type capacity.
VI.
Remove Nth Node From End of List
🧠 Explanation
A two-pass forward-only
approach can be used to remove the Nth node from the end of a linked list. In
the first pass through the linked list, the total length will be calculated.
Once the length is known, the problem of removing the Nth node from the end of
the linked list is converted into removing the (length-n)th node from the front
of the linked list. If N from the example above is equal to the length of the
linked list, then it is time to remove the head of the linked list; in this
case, the function will return head.next. Otherwise, the algorithm will
continue traversing the linked list until it finds the node immediately
preceding the node to be removed. The node to be removed will then be
"skipped" by adjusting the pointer to point to the following node
(i.e., curr.next = curr.next.next). Finally, the original head of the linked
list will continue to be returned.
⚙️ Logic in Steps
1.
You will create a helper function named
length() which will return the total number of nodes contained in the linked
list.
2.
In removeNthFromEnd(), you will find the
total length of the linked list.
3.
If n equals the total length, you will
then remove the head node by returning head.next.
4.
Otherwise, you will traverse the linked
list until you reach the node just before the node that you need to remove.
5.
You will then skip over the target node by
updating the pointer from curr.next = curr.next.next.
6.
Lastly, you will return the original head
of the linked list.
⏱ Time and Space Complexity
Time Complexity O(n)
1. Calculating
the length of the list → O(n)
2. Traversing
to the deletion point → O(n)
Space Complexity
No extra data structures
are used.
📝 Key Takeaways from This Problem
and Solution
1.
The conversion of an issue from Nth from
end to (length - n) from start does provide you with decreased complexity for
logic.
2.
Link nodes are deleted from a linked list
by adjusting pointers and not by moving the elements.
3.
This enables simple and easily understood
code with only two traversals.
4.
Node deletion within a linked list is used
as a means of memory management, for streaming data processing, and as part of
a dynamic data structure.
VII.
Linked List Cycle II
🧠 Explanation
This code uses Floyd’s
Cycle Detection Algorithm (Tortoise and Hare method) to find the entry point of
the cycle within a linked list. To do this, the algorithm first uses two
pointers that travel at different speeds to figure out whether or not the list
has a cycle, then it uses the pointer that traversed into the loop to find
where the cycle started. Two pointers, slow and fast, begin at the head of the
list. The slow pointer moves one node at a time and the fast pointer moves two
nodes at a time. If both pointers meet within the loop area, then there is a
cycle in the linked list.
After the two pointers
meet, we then move the slow pointer back to the head of the list. After that,
both slow and fast pointers will now move one node at a time. When the two
pointers meet again, the node at which they met is the starting point of the cycle;
therefore, we return that node as our result. If the two pointers never meet
while traversing the first phase, then there is no cycle in the linked list and
we simply return None.
⚙️ Logic in Steps
1.
Position both the slow and fast pointers
at the start of linked list.
2.
Next, traverse through the linked list
until either the fast pointer or the next position of the fast pointer are
null.
3.
Then, move the slow pointer forward by one
node and the fast pointer forward by two nodes.
4.
If both the slow pointer and fast pointer
meet during this process, there is a cycle.
5.
If there was no meeting point after
finishing the above loop, there was no cycle.
6.
Reset the slow pointer back to the start
of the linked list.
7.
Now move both the slow and fast pointer by
one node until they again meet.
8.
At that node, will be the start of the
cycle.
9.
This is the node you should return as the
start of the cycle.
⏱ Time and Space Complexity
Time Complexity O(n)
1. Detecting
the cycle
2. Finding
the start of the cycle
Space Complexity O(1)
Only two pointers are
used without additional data structures.
📝 Key Takeaways from This Problem
and Solution
1.
The Floyd Algorithm successfully
identifies cycles by utilizing 2 pointers that each have a distinct velocity.
After identifying a cycle, the algorithm will reset the slower pointer to the
head so that the algorithm can pin-point the true start of the cycle.
2.
The algorithm utilizes constant memory
usage throughout its execution; this allows for optimal results for each
cycle-detection problem.
3.
Cycle-detection techniques are being
utilized across a number of applications including memory management, graph
traversal, and routing systems that have high importance on detecting cycles
due to the potential for causing loops.
VIII.
Reorder List
🧠 Explanation
This program will create
a linked list in this way:
L0 → Ln → L1 → Ln-1 → L2
→ Ln-2 → …
This program creates this
order by using two basic steps. First, it determines where the middle of the
linked list exists by using two pointers (one that moves one step at a time and
another that moves two steps at a time). Second, it reverses the last half of
the linked list so that it is easy to access the last nodes of the list. After
finding the middle of the linked list and having all the second half split into
single nodes and reversed, the first half and last half of the linked list can
be merged together and reordered into the above example. Since this is an in
place operation there is no need to create a new linked list to complete this
operation.
⚙️ Logic in Steps
1. Implement
the slow/fast pointer technique to locate the midpoint of a linked list.
2. Reverse
the second segment.
3. Separate
the first segment from the second segment.
4. Alternative
merge values from both segments according to their position in each.
⏱ Time and Space Complexity
Time Complexity: O(n)
Space
Complexity: O(1)
📝 Key Takeaways from This Problem
and Solution
1.
Combines three core linked list
techniques: middle finding, reversing, and merging.
2.
Uses in-place modification, making it
memory efficient.
3.
This pattern is common in advanced linked
list interview problems
Conclusion
On the surface, Linked Lists appear
straightforward but are actually home to many of the most rewarding
problem-solving techniques that you will see in your technical interviews. The
problems contained in this course have been chosen from a well-respected
Leetcode platform will allow you to develop a greater feel for handling
pointers, applying double-pointer techniques and transforming lists in-place.
When you have learned how to master these techniques of handling Linked Lists,
you will be able to successfully work your way through the majority of Linked
List problems you encounter in your subsequent programming career and further
develop your cumulative algorithmic thought process for addressing any array of
coding challenges that you will be confronted with throughout your entire
programming career.
If you Missed the Previous
Part
If you missed the
previous part of this series, make sure to check out our guide on String
Algorithms, where we solved 8 high-impact problems and explored key patterns
used in coding interviews. String manipulation is one of the most frequently
tested skills in technical interviews, making it an essential topic before
moving to Linked Lists. (dev.to)
Coming Up
Up next, we dive into Hashing,
one of the most powerful techniques for turning slow problems into lightning
fast solutions using hash maps and clever lookups.
Comments
Post a Comment