DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Solve 12 classic linked list interview problems with complete solutions — reorder list, add two numbers, copy list with random pointer, flatten multilevel list, rotate list, remove nth from end, odd-even linked list, merge k sorted lists, and more.
Introduction
This lesson applies everything covered in the linked list section to 12 classic interview problems. Each solution demonstrates a key pattern — the two-pointer technique, dummy head nodes, merging, reversal — and explains why the approach works.
Problem 2 — Add Two Numbers
Problem: Two non-empty linked lists represent non-negative integers in reverse order. Add the two numbers and return the sum as a linked list.
| l1: 2 | 4 → 3 (represents 342) |
| l2: 5 | 6 → 4 (represents 465) |
| Output: 7 | 0 → 8 (represents 807) |
python example
def add_two_numbers(l1, l2):
"""
Simulate manual addition with carry.
Time: O(max(m,n)), Space: O(max(m,n))
"""
dummy = Node(0)
current = dummy
carry = 0
while l1 or l2 or carry:
val1 = l1.data if l1 else 0
val2 = l2.data if l2 else 0
total = val1 + val2 + carry
carry = total // 10
digit = total % 10
current.next = Node(digit)
current = current.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy.nextProblem 3 — Copy List with Random Pointer
Problem: A linked list where each node has next and random pointers. Create a deep copy.
Example
class RandomNode:
def __init__(self, val, next=None, random=None):
self.val = val
self.next = next
self.random = random
def copy_random_list(head):
"""
Hash map approach: old node → new node.
Time: O(n), Space: O(n)
"""
if not head:
return None
old_to_new = {}
# Pass 1: Create all new nodes
current = head
while current:
old_to_new[current] = RandomNode(current.val)
current = current.next
# Pass 2: Set next and random pointers
current = head
while current:
if current.next:
old_to_new[current].next = old_to_new[current.next]
if current.random:
old_to_new[current].random = old_to_new[current.random]
current = current.next
return old_to_new[head]
O(1) space solution (weaving):
python example
def copy_random_list_o1_space(head):
"""
Interleave original and copy nodes, then separate.
Time: O(n), Space: O(1)
"""
if not head:
return None
# Step 1: Insert copy nodes after each original
current = head
while current:
copy = RandomNode(current.val)
copy.next = current.next
current.next = copy
current = copy.next
# Step 2: Set random pointers for copy nodes
current = head
while current:
if current.random:
current.next.random = current.random.next
current = current.next.next
# Step 3: Separate the two lists
current = head
copy_head = head.next
copy_current = copy_head
while current:
current.next = current.next.next
copy_current.next = copy_current.next.next if copy_current.next else None
current = current.next
copy_current = copy_current.next
return copy_headProblem 4 — Reorder List
Problem: Given [L0,L1,...,Ln-1,Ln], reorder it to [L0,Ln,L1,Ln-1,L2,Ln-2,...]. In-place.
Example
[1,2,3,4,5] → [1,5,2,4,3]
[1,2,3,4] → [1,4,2,3]
python example
def reorder_list(head):
"""
Algorithm:
1. Find middle → split into two halves
2. Reverse second half
3. Merge the two halves alternately
Time: O(n), Space: O(1)
"""
if not head or not head.next:
return
# Step 1: Find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Step 2: Reverse second half
second = slow.next
slow.next = None # Split
prev = None
while second:
next_node = second.next
second.next = prev
prev = second
second = next_node
second = prev # Head of reversed second half
# Step 3: Merge alternately
first = head
while second:
tmp1 = first.next
tmp2 = second.next
first.next = second
second.next = tmp1
first = tmp1
second = tmp2Problem 5 — Rotate List by K Positions
Problem: Rotate the list to the right by k places.
Example
[1,2,3,4,5], k=2 → [4,5,1,2,3]
python example
def rotate_right(head, k):
"""
1. Find length and tail
2. k = k % length (handle large k)
3. New tail is at position (length - k - 1) from start
4. Break the list and re-link
Time: O(n), Space: O(1)
"""
if not head or not head.next or k == 0:
return head
# Step 1: Find length and tail
tail = head
length = 1
while tail.next:
tail = tail.next
length += 1
# Step 2: Normalize k
k = k % length
if k == 0:
return head
# Step 3: Find new tail (length - k - 1 steps from head)
new_tail = head
for _ in range(length - k - 1):
new_tail = new_tail.next
# Step 4: Re-link
new_head = new_tail.next
new_tail.next = None
tail.next = head
return new_headProblem 6 — Odd-Even Linked List
Problem: Group all odd-indexed nodes first, then all even-indexed nodes. Maintain relative order. O(1) space.
Example
[1,2,3,4,5] → [1,3,5,2,4]
python example
def odd_even_list(head):
"""
Maintain two separate chains: odd-indexed and even-indexed.
Connect odd chain tail to even chain head.
Time: O(n), Space: O(1)
"""
if not head:
return head
odd = head
even = head.next
even_head = even # Save even head for reconnection
while even and even.next:
odd.next = even.next # Odd → next odd
odd = odd.next # Advance odd
even.next = odd.next # Even → next even
even = even.next # Advance even
odd.next = even_head # Connect odd tail to even head
return headProblem 7 — Merge K Sorted Lists
Problem: Merge k sorted linked lists into one sorted list.
python example
import heapq
def merge_k_lists(lists):
"""
Min-heap approach: maintain a heap of the current minimum across all lists.
Time: O(n log k), Space: O(k)
where n = total nodes, k = number of lists
"""
heap = [] # (value, list_index, node)
# Initialize heap with the head of each list
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.data, i, node))
dummy = Node(0)
current = dummy
while heap:
val, i, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.data, i, node.next))
return dummy.nextDivide and conquer approach — O(n log k), O(log k) space:
Example
def merge_k_lists_divide(lists):
if not lists:
return None
if len(lists) == 1:
return lists[0]
mid = len(lists) // 2
left = merge_k_lists_divide(lists[:mid])
right = merge_k_lists_divide(lists[mid:])
return merge_sorted(left, right) # O(n) merge
def merge_sorted(l1, l2):
dummy = Node(0)
current = dummy
while l1 and l2:
if l1.data <= l2.data:
current.next = l1; l1 = l1.next
else:
current.next = l2; l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.next
Problem 8 — Flatten a Multilevel Doubly Linked List
Problem: A doubly linked list where nodes can have a child pointer to another doubly linked list. Flatten it so all nodes are in a single level.
python example
def flatten(head):
"""
When we encounter a node with a child, insert the child list inline.
Time: O(n), Space: O(1)
"""
if not head:
return head
current = head
while current:
if current.child:
child = current.child
next_node = current.next
# Connect current → child
current.next = child
child.prev = current
current.child = None
# Find tail of child list
tail = child
while tail.next:
tail = tail.next
# Connect child tail → next_node
tail.next = next_node
if next_node:
next_node.prev = tail
current = current.next
return headProblem 9 — Sort List (O(n log n), O(1) Space)
python example
def sort_list(head):
"""
Merge sort on linked list.
Time: O(n log n), Space: O(log n) for recursion.
"""
if not head or not head.next:
return head
# Find middle and split
mid = find_middle_for_sort(head)
right = mid.next
mid.next = None
left = sort_list(head)
right = sort_list(right)
return merge_sorted(left, right)
def find_middle_for_sort(head):
"""Returns the node just before the middle (for clean splitting)."""
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowProblem 10 — Linked List Cycle II (Find Cycle Start)
python example
def detect_cycle(head):
"""
Return the node where the cycle begins, or None.
Floyd's two-phase algorithm.
Time: O(n), Space: O(1)
"""
slow = fast = head
# Phase 1: Detect meeting point
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # No cycle
# Phase 2: Find cycle start
# Mathematical proof: distance from head to cycle start
# equals distance from meeting point to cycle start
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # Cycle startProblem 11 — Swap Nodes in Pairs
Problem: Swap every two adjacent nodes. Do not change values, only links.
Example
[1,2,3,4] → [2,1,4,3]
python example
def swap_pairs(head):
"""
Iterative: use dummy head and prev pointer to swap pairs.
Time: O(n), Space: O(1)
"""
dummy = Node(0)
dummy.next = head
prev = dummy
while prev.next and prev.next.next:
first = prev.next
second = prev.next.next
# Swap
prev.next = second
first.next = second.next
second.next = first
# Advance
prev = first
return dummy.nextProblem 12 — Maximum Twin Sum
Problem: In a linked list of even length n, the twin of node i is node (n-1-i). Find the maximum twin sum.
Example
[5,4,2,1] → twins: (5,1) and (4,2) → max twin sum = 6
python example
def pair_sum(head):
"""
Find middle → reverse second half → add corresponding nodes.
Time: O(n), Space: O(1)
"""
# Find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev = None
current = slow
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
# Compare first half with reversed second half
max_sum = 0
left = head
right = prev
while right:
max_sum = max(max_sum, left.data + right.data)
left = left.next
right = right.next
return max_sumPattern Summary
| Problem | Pattern | Time | Space |
|---|---|---|---|
| Remove nth from end | Two pointers, gap n | O(n) | O(1) |
| Add two numbers | Digit-by-digit simulation | O(max(m,n)) | O(n) |
| Copy with random pointer | Hash map or weaving | O(n) | O(n)/O(1) |
| Reorder list | Split + reverse + merge | O(n) | O(1) |
| Rotate list | Find tail + re-link | O(n) | O(1) |
| Odd-even list | Two chains | O(n) | O(1) |
| Merge k sorted | Min-heap | O(n log k) | O(k) |
| Flatten multilevel | Inline insertion | O(n) | O(1) |
| Sort list | Merge sort | O(n log n) | O(log n) |
| Cycle detection II | Floyd's two-phase | O(n) | O(1) |
| Swap pairs | Dummy + iterative | O(n) | O(1) |
| Maximum twin sum | Split + reverse | O(n) | O(1) |
Summary
The linked list section covers the complete spectrum:
- Foundation: Node structure, types, memory model
- Operations: Insert, delete, search, traverse for all three types
- Core techniques: Two-pointer (slow-fast), dummy head, reversal
- Classic problems: The 12 problems above cover every important pattern
The two-pointer technique and the three-pointer reversal are the backbone. Everything else is a variation or combination of these fundamental patterns.
*Linked Lists section complete. Next: Stacks — Introduction*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Linked List Interview Problems — 12 Classic Problems with Complete Solutions.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, linked, lists, list
Related Data Structures & Algorithms Topics
Continue learning this concept
Linked ListsCircular Linked List — Structure, Operations, and ApplicationsMaster circular linked lists — singly and doubly circular variants, complete implementation with insertion and deletion, traversal without infinite loops, detecting circular structure, and real-world applications in round-robin scheduling and circular buffers.Linked ListsDoubly Linked List — Complete Implementation with Bidirectional OperationsA complete guide to doubly linked lists — node structure with prev and next pointers, all operations with O(1) and O(n) complexities, comparison with singly linked lists, LRU Cache implementation using doubly linked list and hash map, and interview problems.Linked ListsLinked Lists — A Complete Introduction with Memory Model and TypesLearn everything about linked lists from scratch — what they are, how they are stored in memory with pointers, the difference from arrays, all three types (singly, doubly, circular), node structure, and the fundamental operations with time and space complexity.Linked ListsLinked List Operations — Every Technique with Code and ComplexityA complete reference of all essential linked list operations and patterns — reversal, merge, cycle detection, finding nth from end, palindrome check, flattening, sorting, partitioning, and the two-pointer technique — each with full implementation, complexity analysis, and explanations.Linked ListsReverse Linked List — All Approaches from Basic to AdvancedMaster every approach to reversing a linked list — iterative reversal with three pointers, recursive reversal with complete derivation, reversing a sublist, reversing k-groups, reversing alternating k-groups, and why the iterative approach is always preferred in interviews.Linked ListsSingly Linked List — Complete Implementation with All OperationsMaster the singly linked list with complete Python and Java implementations of every operation — insert at head/tail/position, delete by value/position, search, reverse, detect and remove loops, find middle, merge sorted lists, and all classic interview techniques.