Day 13 of 30 days of Data Structures and Algorithms and System Design Simplified — Linked List
Welcome back peeps. Hope all’s well. In this post we will cover Linked List as follows —
What and Why Linked List(in 2–3 sentences)?
How does Linked List work?
Important Patterns and Techniques in Linked List Questions
Most Important Questions with Solutions
Tips and Techniques to solve Linked List Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Linked List
Importance : Very High
Note : New Linked List questions with solutions are added every day. So keep checking this post daily.
Let’s dive in!
What is Linked List?
Linked List is a data structure which has structure as shown below —
Each node in the linked list is nothing but data+next. Data stores the value and next stores the address of the next node.
That’s all you need to know.
Examples of Linked List problems —
Remove N node from the end of List
Reorder List
Remove Linkedin List Elements
Delete the Middle Node of a Linked List
Max twin sum of a Linked List etc
How does Linked List work?
A linked list is a data structure that consists of a sequence of elements, called nodes, where each node contains a reference (or “link”) to the next element in the list. Linked lists are often used to implement dynamic data structures, where the number of elements can change during the execution of a program.
A linked list is typically made up of two parts: the data, which is stored in the node, and the reference (or “next” pointer), which points to the next node in the list. Each node also contains a reference to the previous node, allowing for efficient insertion and deletion operations.
Linked List most important attribute is the address which links one node to the other.
Linked List has methods (that you should know) —
Important Patterns and Techniques in Linked List Questions
Important patterns and techniques in linked list questions include understanding the basic operations of a linked list, such as insertion, deletion, and traversal, and using linked lists in the design of algorithms, such as sorting and searching.
Only three things —
- If you know how to traverse the linked list starting from head/any node especially when the node points to NULL
- How to manipulate the next or previous pointers.
- How to handle complex operations — like add node, delete node, replace node, double pointers operations etc.
To summarize, have a good grip — basics of linked list, must know how to manipulate the pointers and should be able to communicate every step — the logic/main point while solving the question .
Patterns → Questions like below belong to Linked List( not limited to):
Sum of two Linked List’
Swapping Nodes in a Linked List
Reverse nodes in K — group
Remove N node from the end of List
Reorder List
Remove Linkedin List Elements
Delete the Middle Node of a Linked List
Max twin sum of a Linked List etc
Most Important Questions with Solutions
Note : New Linked List questions with solutions are added every day. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Linked List questions.
Merge k Sorted Lists
Question —
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example —
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]Solution :
Main Logic/Idea —
First break the list into two lists ( list1 and list2 ) using alternate positions/indexes. Next, merge these two lists using a temp linked list node and keep merging based on the values ( i.e if list1 value is greater/smaller than list2 etc.)
Implementation —
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists or len(lists) == 0:
return None
while len(lists) > 1:
finalList=[]
for i in range(0,len(lists),2):
list1 = lists[i]
list2 = lists[i+1] if (i+1) < len(lists) else None
finalList.append(self.subMerge(list1,list2))
lists = finalList
return lists[0]
def subMerge(self,list1,list2):
temp = ListNode()
tail = temp
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1 :
tail.next = list1
elif list2:
tail.next = list2
return temp.nextQuestion Link
Similar Pattern —
Minimum Cost to Hire K Workers
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Delete the Middle Node of a Linked List
Question —
You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.
- For
n=1,2,3,4, and5, the middle nodes are0,1,1,2, and2, respectively.
Example —
Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]Solution:
Main Logic/Idea —
The crux of this problem is to copy the data of temporary node which is the middle’s next node to the middle node and make the middle node next point to temp’s next.
Implementation —
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head and head.next: return head
temp = slow = fast = head
prev, curr = None, 0
while temp:
temp = temp.next
curr += 1
while fast.next and fast.next.next:
prev = slow
slow = slow.next
fast = fast.next.next
if curr % 2 != 0:
prev.next = slow.next
slow = None
else:
prev = slow
slow = slow.next
prev.next= slow.next
slow = None
return headQuestion Link
Similar Pattern —
Remove Nth Node From End of List
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Merge Two Sorted Lists
Question —
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example —
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]Solution:
Main Logic/Idea —
Using temp as temporary linked list node, compare the values of list1 and list2 and merge it ( by pointing the next node of temp to be list1 or list2).
In case length of list1 and list2 are not equal then add the remaining nodes in list1 or list2 to the temporary list node.
Implementation —
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
temp = ListNode()
tail = temp
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail= tail.next
if list1:
tail.next = list1
elif list2:
tail.next = list2
return temp.nextQuestion Link
Similar Pattern —
Add Two Polynomials Represented as Linked Lists
Longest Common Subsequence Between Sorted Arrays
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Reorder List
Question —
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → LnReorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
Example —
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]Solution:
Main Logic/Idea —
Find the mid of the list and reverse the links using two pointers.
Implementation —
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
first, second = head, head.next
while second and second.next:
first = first.next
second = second.next.next
mid = first.next
pNode, first.next = None, None
while mid:
t1 = mid.next
mid.next = pNode
pNode = mid
mid = t1
t,v = head, pNode
while v:
t2,t3 = t.next, v.next
t.next = v
v.next = t2
t,v = t2,t3Question Link
Similar Pattern —
Delete the Middle Node of a Linked List
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Complexity Analysis
Complexity Analysis of Linked List —
Insert in the beginning: O(1)
Insert at the end: O(1)
Search: O(n)
Indexing : O(n)
Remove in the beginning: O(1)
Remove from end: O(n)
Remove in middle : O(n)
Tips and Techniques to solve Linked List Questions Fast.
Remember the basic structure of a Linked List — Value and Address.
Keep in mind three things —
- If you know how to traverse the linked list starting from head/any node especially when the node points to NULL
- How to manipulate the next or previous pointers.
- How to handle complex operations — like add node, delete node, replace node, double pointers operations etc.
- Know how to implement recursion.
That’s it for now. Day 14 : Stack coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
