Ankit Kashyap

Patterns

Patterns

Linked List Reversal Patterns

  • Reversal usually means carrying three pointers: prev, curr, and next. Save next before changing curr.next.
  • If the problem mutates the head or a sub-list, think about whether a dummy node is needed to reconnect the result cleanly.
  • For palindrome/reorder style problems, find the middle with fast/slow, reverse one half, then compare or merge.
  • Interview trap: keep references to the node before the reversed section and the node after it.
function reverseList(head) {
  let prev = null;
  let curr = head;
 
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
 
  return prev;
}

Famous questions:

  • 206. Reverse Linked List
    1. Reverse Linked List II
    1. Reorder List
    1. Palindrome Linked List
    1. Reverse Nodes in k-Group

LCA In Binary Trees

  • For a normal binary tree, DFS both sides; if both sides return a node, the current root is the LCA.
  • If current node is p or q, return it upward immediately because a node can be an ancestor of itself.
  • For a BST, use value ordering: if both targets are smaller go left, if both larger go right, else current node is the split point.
  • Interview trap: confirm whether both nodes are guaranteed to exist in the tree.
function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
 
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
 
  if (left && right) return root;
  return left || right;
}

Famous questions:

  • 236. Lowest Common Ancestor of a Binary Tree
    1. Lowest Common Ancestor of a Binary Search Tree
    1. Lowest Common Ancestor of a Binary Tree II
    1. Lowest Common Ancestor of a Binary Tree III
    1. Lowest Common Ancestor of Deepest Leaves

Undirected Graph vs Tree

  • A tree is just an undirected graph with two guarantees: connected and no cycle.
  • For n nodes, a valid tree must have exactly n - 1 edges. If the edge count is wrong, return false immediately.
  • After the edge-count check, one BFS/DFS from node 0 should visit every node.
  • Interview trap: in an undirected graph, seeing the parent again is not a cycle. Either track parent during DFS or use the edges.length === n - 1 shortcut plus connectedness.
function validTree(n, edges) {
  if (edges.length !== n - 1) return false;
 
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }
 
  const visited = new Set([0]);
  const stack = [0];
 
  while (stack.length) {
    const node = stack.pop();
 
    for (const neighbor of graph[node]) {
      if (visited.has(neighbor)) continue;
      visited.add(neighbor);
      stack.push(neighbor);
    }
  }
 
  return visited.size === n;
}

Famous questions:

Graph Edge Reversal

  • When a directed edge might need reversal, traverse the graph as undirected but store a cost for each direction.
  • Add a -> b with cost 1 if using that direction is “wrong” for the chosen root, and b -> a with cost 0.
  • For one root, DFS/BFS and sum the costs.
  • For every possible root in a tree, compute the answer for root 0, then reroot:
    • moving across an original parent -> child edge reduces the cost by 1
    • moving across an original child -> parent edge increases the cost by 1
function minReorder(n, connections) {
  const graph = Array.from({ length: n }, () => []);
 
  for (const [a, b] of connections) {
    graph[a].push([b, 1]);
    graph[b].push([a, 0]);
  }
 
  let changes = 0;
  const visited = new Set([0]);
  const stack = [0];
 
  while (stack.length) {
    const node = stack.pop();
 
    for (const [neighbor, cost] of graph[node]) {
      if (visited.has(neighbor)) continue;
      visited.add(neighbor);
      changes += cost;
      stack.push(neighbor);
    }
  }
 
  return changes;
}

Famous questions:

Backlinks