All Roadmaps›🧠 Data Structures & Algorithms›Phase 2›Recursion-Based Structures (Linked List Ops, Nested Structures)

Recursion-Based Structures (Linked List Ops, Nested Structures)

0/14 in this phase0/57 across the roadmap

📖 Concept

Many data structure operations are naturally recursive. Understanding how to think recursively about linked lists, nested arrays, and tree-like structures is essential for interviews.

Why recursion fits certain structures:

  • Linked lists are recursive by definition: a node + a smaller linked list
  • Nested arrays/objects have unknown depth — recursion handles any depth
  • Trees are recursive: a node + left subtree + right subtree

The recursive linked list mental model:

[1] → [2] → [3] → null
 ↓
 1 + recurse([2] → [3] → null)
       ↓
       2 + recurse([3] → null)
             ↓
             3 + recurse(null) → base case: 0

Key patterns:

  1. Process current node + recurse on rest (linked list sum, length, contains)
  2. Recurse first, then process (reverse linked list, reverse nested)
  3. Recurse on all children (flatten nested arrays, deep clone objects)
  4. Divide into halves (merge sort on linked list)

🏠 Real-world analogy: Recursion on a linked list is like a relay race — each runner (node) does their part and passes the baton (result) to the next runner. The last runner (base case) sends the result back.

💻 Code Example

codeTap to expand ⛶
1// RECURSIVE LINKED LIST OPERATIONS
2

3class ListNode {
4  constructor(val, next = null) {
5    this.val = val;
6    this.next = next;
7  }
8}
9

10// Sum all values — recursively
11function sumList(head) {
12  if (!head) return 0;                    // Base case
13  return head.val + sumList(head.next);    // Current + rest
14}
15

16// Reverse linked list — recursively
17function reverseListRecursive(head) {
18  if (!head || !head.next) return head;   // Base case
19  const newHead = reverseListRecursive(head.next); // Recurse to end
20  head.next.next = head;                   // Reverse pointer
21  head.next = null;                        // Clean old pointer
22  return newHead;
23}
24

25// Check if linked list contains value
26function contains(head, target) {
27  if (!head) return false;
28  if (head.val === target) return true;
29  return contains(head.next, target);
30}
31

32// DEEP FLATTEN NESTED ARRAYS
33function deepFlatten(arr) {
34  const result = [];
35  for (const item of arr) {
36    if (Array.isArray(item)) {
37      result.push(...deepFlatten(item));  // Recurse into nested
38    } else {
39      result.push(item);
40    }
41  }
42  return result;
43}
44// [1, [2, [3, [4]], 5]] → [1, 2, 3, 4, 5]
45

46// DEEP CLONE OBJECTS — handles nested objects/arrays
47function deepClone(obj) {
48  if (obj === null || typeof obj !== 'object') return obj;
49  if (Array.isArray(obj)) return obj.map(item => deepClone(item));
50  const clone = {};
51  for (const key of Object.keys(obj)) {
52    clone[key] = deepClone(obj[key]);
53  }
54  return clone;
55}
56

57// TypeScript — Deep nested sum
58interface NestedInteger {
59  value?: number;
60  list?: NestedInteger[];
61}
62

63function nestedSum(nested: NestedInteger[]): number {
64  let total = 0;
65  for (const item of nested) {
66    if (item.value !== undefined) {
67      total += item.value;
68    } else if (item.list) {
69      total += nestedSum(item.list);
70    }
71  }
72  return total;
73}
74

75// MERGE SORT ON LINKED LIST — Divide & Conquer
76function mergeSortList(head) {
77  if (!head || !head.next) return head;
78  const mid = getMiddle(head);
79  const right = mid.next;
80  mid.next = null; // Split
81  return mergeTwoLists(mergeSortList(head), mergeSortList(right));
82}
83

84function getMiddle(head) {
85  let slow = head, fast = head.next;
86  while (fast && fast.next) {
87    slow = slow.next;
88    fast = fast.next.next;
89  }
90  return slow;
91}
92

93function mergeTwoLists(l1, l2) {
94  const dummy = new ListNode(0);
95  let curr = dummy;
96  while (l1 && l2) {
97    if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
98    else { curr.next = l2; l2 = l2.next; }
99    curr = curr.next;
100  }
101  curr.next = l1 || l2;
102  return dummy.next;
103}

🏋️ Practice Exercise

Practice Problems:

  1. Find the length of a linked list recursively
  2. Print a linked list in reverse order (without reversing it) using recursion
  3. Deep flatten a nested array of any depth
  4. Deep clone a nested object (handle arrays, objects, primitives)
  5. Recursively sum all numbers in a nested structure like NestedInteger
  6. Sort a linked list using merge sort (recursive divide & conquer)
  7. Remove all occurrences of a value from a linked list recursively
  8. Check if two nested structures are deeply equal
  9. Recursively find the maximum depth of a nested array
  10. Convert a nested list to a flat list preserving order

⚠️ Common Mistakes

  • Not identifying the base case for recursive linked list operations — it's usually !head or !head.next

  • Forgetting to return the new head after recursive reversal — the recursion returns the new head all the way up

  • Stack overflow on deeply nested structures — convert to iterative with explicit stack for very deep nesting

  • Modifying the original data structure when a deep clone is needed — always create new nodes/objects

  • Not handling circular references in deep clone — add a visited set for production code

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Recursion-Based Structures (Linked List Ops, Nested Structures)

← PreviousSets & Maps — Built-in & CustomNext →Matrices & 2D Arrays