function levelOrderZigzag(root) {
let queue = [root], result = [], direction = 0;
function process(node) {
result.push(node.val); //?
}
while (queue.length) {
let level = [];
while(queue.length) {
const node = queue.pop();
process(node);
if (direction === 0) {
if (node.left) level.push(node.left);
if (node.right) level.push(node.right);
}
else {
if (node.right) level.push(node.right);
if (node.left) level.push(node.left);
}
}
direction ^= 1;
queue = level;
}
return result; //?
}
function levelOrder(root) {
let queue = [root], result = [];
function process(node) {
result.push(node.val);
}
while (queue.length) {
const node = queue.pop();
process(node);
if (node.left) queue.unshift(node.left);
if (node.right) queue.unshift(node.right);
}
return result; //?
}
Categories
LinkedList Middle Node
let middleNode = function(head) {
let slow = head, fast = head;
while (fast) {
if (fast.next !== null && fast.next.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
else if (fast.next) {
slow = slow.next;
break;
}
else {
break;
}
}
return slow;
};
Categories
Reverse Middle of LinkedList
// m = start of items to reverse, n = end of item to reverse
let reverseBetween = function(head, m, n) {
let node = head,
result = [],
reversed = [],
counter = 1;
while (node) {
let next = node.next;
if (counter < m) {
result.push(node); //?
}
if (counter >=m && counter <= n) {
node.next = null;
reversed.push(node); //?
}
else if (counter > n) {
// all reversals are done
// drain reversed into result
while (reversed.length) {
result.push(reversed.pop()); //?
}
result.push(node);
break;
}
counter++;
node = next;
}
// if reversals are done at the end of the linkedlist
while (reversed.length) {
result.push(reversed.pop()); //?
}
let root = new ListNode(0), tail = root;
while (result.length) {
tail.next = result.shift();
tail = tail.next;
console.log(tail);
}
return root.next; //?
};
Categories
Reverse LinkedList (Iterative)
let reverseLinkedList = function(root) {
let reverse = new ListNode(0);
let node = root;
while (node) {
let toAdd = node;
let next = node.next;
let reversedNext = reverse.next;
toAdd.next = reversedNext;
reverse.next = toAdd; //
node = next;
}
return reverse.next;
}
let reverseLinkedList = function(root, reverse = new ListNode(0)) {
if (root) {
let toAdd = root;
let next = root.next;
let reversedNext = reverse.next;
toAdd.next = reversedNext;
reverse.next = toAdd;
reverseLinkedList(next, reverse);
}
return reverse.next;
}
function fib(x) {
let cache = {}
function fibInternal(n) {
if(n == 0) return 0;
if(n <= 2) return 1;
if (cache[n]) return cache[n];
const result = fibInternal(n - 1) + fibInternal(n - 2);
cache[n] = result;
return result;
}
return fibInternal(x)
}
Categories
Fibonacci (Iterative)
function fib(n) {
if(n === 0) return 0;
if(n <= 2) return 1;
let x = 1, y = 2;
for(let i = 3; i < n; i++) {
let oldX = x;
x = y;
y = y + oldX; /*?.*/
}
return y;
}
let intToRoman = function(num) {
const mapping = {
1000: 'M',
900: 'CM',
500: 'D',
400: 'CD',
100: 'C',
90: 'XC',
50: 'L',
40: 'XL',
10: 'X',
9: 'IX',
5: 'V',
4: 'IV',
1: 'I'
}
let result = "";
for(let divisor of [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]) {
if (num >= divisor) {
let quotient = Math.floor(num / divisor);
result = result + mapping[divisor].repeat(quotient);
num = num % divisor;
}
}
return result;
}
let lookAndSay = function(nth, number = "1") {
if (nth === 1) return number;
let index = 0,
counter = 1,
currentNumber = "";
let result = "";
while (index < number.length) {
if (index === 0) {
currentNumber = number[index];
}
else if (currentNumber === number[index]) {
counter++;
}
else if (currentNumber !== number[index]) {
result = `${result}${counter}${currentNumber}`;//?
counter = 1;
currentNumber = number[index];
}
index++;
}
result = `${result}${counter}${currentNumber}`;//?
return lookAndSay(--nth, result);
}