# leetcode 各种题

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
  let len1 = m - 1;
  let len2 = n - 1;
  let len = m + n - 1;
  while (len1 >= 0 && len2 >= 0) {
    // 注意--符号在后面，表示先进行计算再减1，这种缩写缩短了代码
    nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
  }
  function arrayCopy(src, srcIndex, dest, destIndex, length) {
    dest.splice(destIndex, length, ...src.slice(srcIndex, srcIndex + length));
  }
  // 表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为len2+1
  arrayCopy(nums2, 0, nums1, 0, len2 + 1);
};

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
  let hash = new Map();
  let res = [];
  for (let i = 0; i < nums1; i++) {
    if (hash.has(nums1[i])) {
      hash.set(nums1[i], hash.get(nums1[i]) + 1);
    } else {
      hash.set(nums1[i], 1);
    }
  }
  for (let j = 0; j < nums2.length; j++) {
    if (hash.has(nums2[j]) && hash.get(nums2[j]) > 0) {
      console.log(11);
      res.push(nums2[j]);
      hash.set(nums2[j], hash.get(nums2[j]) - 1);
    }
  }
  return res;
};

intersect([1, 2, 2, 1], [2, 2]);

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  let l = nums1.length - 1;
  let r = nums2.length - 1;
  let res = [];
  while (l > 0 && r > 0) {
    if (nums1[l] === nums2[r]) {
      res.push(nums1[l]);
      l--;
      r--;
    } else if (nums1[l] < nums2[r]) {
      r--;
    } else {
      l--;
    }
  }
  console.log(res);
  return res;
};

intersect([1, 2, 2, 1], [2, 2]);

/**
 * @param {string} name
 * @param {string} typed
 * @return {boolean}
 */
var isLongPressedName = function(name, typed) {
  let l = 0;
  let r = 0;
  while (l < name.length) {
    if (name[l] === typed[r]) {
      l++;
      r++;
    } else if (name[l - 1] === typed[r]) {
      r++;
    } else {
      return false;
    }
  }
  return true;
};

isLongPressedName("alex", "aaleex");

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
  s = s.replace(/[^0-9a-zA-Z]/g, "").toLowerCase();
  let l = 0;
  let r = s.length - 1;
  while (l < r) {
    if (s[l] !== s[r]) {
      return false;
    }
    l++;
    r--;
  }
  return true;
};

var isPalindrome = function(head) {
  let nums = [];
  while (head) {
    nums.push(head.val);
    head = head.next;
  }

  while (nums.length > 1) {
    if (nums.pop() != nums.shift()) return false;
  }
  return true;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
  // 首先找到链表的中点
  if (head === null) true;
  let middle = head,
    end = head;
  let num = 0; // 链表节点的总个数
  while (end !== null) {
    num++;
    end = end.next;
    if ((num & 1) === 0) {
      middle = middle.next;
    }
  }
  // 然后反转前一部分链表
  let pre = null,
    cur = head,
    next;
  while (cur !== middle) {
    next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
  // 最后根绝链表总数的奇偶性不同选取左右部分的起始节点，然后开始遍历
  let leftStart = pre,
    rightStart;
  if (num & 1) {
    // 如果链表节点个数是奇数，那么middle指向的是链表的中点
    rightStart = middle.next;
  } else {
    // 如果链表节点个数是偶数，那么middle指向的是后半部第一个节点
    rightStart = middle;
  }
  while (leftStart !== null && rightStart !== null) {
    if (leftStart.val !== rightStart.val) {
      return false;
    }
    leftStart = leftStart.next;
    rightStart = rightStart.next;
  }
  return true;
};

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function(nums, k) {
  if (k < 0 || nums.length < 2) {
    return 0;
  }
  const length = nums.length;
  let count = 0;
  let start = 0;
  let end = 1;
  nums = nums.sort((a, b) => a - b);
  while (start < length && end < length) {
    if (start > 0 && nums[start] === nums[start - 1]) {
      start++;
    }
    if (nums[end] - nums[start] > k) {
      start++;
    } else if (nums[end] - nums[start] < k || start == end) {
      end++;
    } else if (nums[end] - nums[start] == k) {
      count++;
      end++;
      while (end < length && nums[end] === nums[end - 1]) {
        end++;
      }
    }
  }
  return count;
};

findPairs([3, 1, 4, 1, 5], 2);

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
  let slow = nums[0];
  let fast = nums[slow];
  while (slow != fast) {
    slow = nums[slow];
    fast = nums[nums[fast]];
  }
  fast = 0;
  while (fast != slow) {
    console.log(nums[slow]);
    slow = nums[slow];
    fast = nums[fast];
  }

  return nums[slow];
};

findDuplicate([1, 3, 4, 2, 2]);

/**
 * @param {number[][]} A
 * @param {number[][]} B
 * @return {number[][]}
 */
var intervalIntersection = function(A, B) {
  if (A == [] || B == []) {
    return [];
  }
  var result = [];
  var a = A[0];
  var b = B[0];
  var m, n;
  var iA = 1;
  var iB = 1;
  while (iA <= A.length && iB <= B.length) {
    if (a[0] >= b[0]) {
      m = a[0];
      if (a[1] > b[1]) {
        n = b[1];
      } else {
        n = a[1];
      }
    } else {
      m = b[0];
      if (a[1] > b[1]) {
        n = b[1];
      } else {
        n = a[1];
      }
    }
    if (n >= m) {
      var tmp = [];
      tmp[0] = m;
      tmp[1] = n;
      result[result.length] = tmp;
    }
    if (b[1] >= a[1]) {
      a = A[iA];
      iA++;
    } else {
      b = B[iB];
      iB++;
    }
  }
  return result;
};

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
  let i = 0;
  let j = height.length - 1;
  let maxArea = 0;
  while (i < j) {
    maxArea = Math.max((j - i) * Math.min(height[i], height[j]), maxArea);
    if (height[i] <= height[j]) {
      i++;
    } else {
      j--;
    }
  }
  return maxArea;
};

maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]);

var sortColors = function(nums) {
  if (nums.length > 1) {
    var p0 = 0,
      p2 = nums.length - 1,
      curr = 0;
  }
  while (curr <= p2) {
    if (nums[curr] == 0) {
      [nums[p0], nums[curr]] = [nums[curr], nums[p0]];
      p0++;
      curr++;
    } else if (nums[curr] == 2) {
      [nums[p2], nums[curr]] = [nums[curr], nums[p2]];
      p2--;
    } else {
      curr++;
    }
  }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
  let before_head = new ListNode(null);
  let before = before_head;
  let after_head = new ListNode(null);
  let after = after_head;
  while (head !== null) {
    if (head.val < x) {
      before.next = head;
      before = before.next;
    } else {
      after.next = head;
      after = after.next;
    }
    head = head.next;
  }
  after.next = null;
  before.next = after_head.next;
  return before_head.next;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
//  拆分逻辑 先获取首次相遇的时候的节点
var getCycleFistMeetNode = function(head) {
  if (!head || !head.next) {
    return false;
  }
  let slow = head.next;
  let fast = head.next.next;
  while (fast) {
    if (slow == fast) {
      return fast;
    }
    slow = slow.next;
    if (fast.next && fast.next.next) {
      fast = fast.next.next;
    } else {
      fast = null;
    }
  }
  return false;
};
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
  // 判断是否获取到了首次相遇的节点
  let firstNode = getCycleFistMeetNode(head)
    ? getCycleFistMeetNode(head)
    : false;
  let cur = head;
  if (firstNode) {
    while (firstNode) {
      if (cur === firstNode) {
        return cur;
      }
      cur = cur.next;
      firstNode = firstNode.next;
    }
  }
  return null;
};

const test = head => {
  if (!head || !head.next) {
    return false;
  }
  let slow = head.next;
  let fast = head.next.next;
  while (fast) {
    if (slow == fast) {
      return fast;
    } else {
      slow = slow.next;
      if (fast.next && fast.next.next) {
        fast = fast.next.next;
      } else {
        fast = null;
      }
    }
  }
  return false;
};

var detectCycle = function(head) {
  let firstNode = test(head);
  let newNode = head;
  if (firstNode) {
    while (newNode) {
      if (newNode == firstNode) {
        return newNode;
      }
      newNode = newNode.next;
      firstNode = firstNode.next;
    }
  }
  return null;
};

/**
 * @param {number[]} A
 * @param {number} K
 * @return {number}
 */
var longestOnes = function(A, K) {
  let i = 0;
  let j = 0;
  let left = K;
  let res = 0;
  while (j < A.length) {
    if (A[j] === 0) {
      if (left === 0) {
        if (A[i] === 0) {
          left++;
        }
        i++;
      } else {
        left--;
        j++;
      }
    } else {
      j++;
    }
    res = Math.max(res, j - i);
  }
  return res;
};

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
  let start = 0;
  let hash = {};
  let charNum = 0;
  let longNum = 0;
  for (let i = 0, len = s.length; i < len; i++) {
    let c1 = s[i];
    hash[c1] = hash[c1] || 0;
    hash[c1] += 1;
    charNum = Math.max(charNum, hash[c1]);
    if (i - start + 1 - charNum > k) {
      hash[s[start]]--;
      start++;
    }
    longNum = Math.max(longNum, i - start + 1);
  }
  return longNum;
};

/**
 * @param {string} s
 * @param {string[]} d
 * @return {string}
 */
var findLongestWord = function(s, d) {
  const sl = s.length;
  const dl = d.length;
  if (sl === 0 || dl === 0) {
    return "";
  }
  let res = "";
  for (let i = 0; i < dl; i++) {
    let left = 0;
    let right = 0;
    const il = d[i].length;
    while (left < sl && right < il) {
      if (s[left] === d[i][right]) {
        right++;
      }
      left++;
    }
    if (right == il) {
      if (res.length > right) {
        res = res;
      } else if (res.length == right) {
        res = res <= d[i] ? res : d[i];
      } else {
        res = d[i];
      }
    }
  }
  return res;
};

var s = "bab",
  d = ["ba", "ab", "a", "b"];

findLongestWord(s, d);

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
  const len = nums.length;
  if (len < 3) {
    return null;
  }
  nums = nums.sort((a, b) => {
    return a - b;
  });

  let res = nums[0] + nums[1] + nums[2];
  for (let i = 0; i < len; i++) {
    let start = i + 1;
    let end = len - 1;
    while (start < end) {
      const num = nums[start] + nums[end] + nums[i];
      const diff = num - target;
      if (Math.abs(diff) < Math.abs(target - res)) {
        res = num;
      }
      if (diff > 0) {
        end--;
      } else if (diff < 0) {
        start++;
      } else {
        return res;
      }
    }
  }
  return res;
};

threeSumClosest([-1, 2, 1, -4], 1);

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
  if (!head) return null;
  let curr = head,
    tmp = null,
    n = 0;
  while (curr) {
    n++;
    if (!curr.next) {
      curr.next = head;
      break;
    }
    curr = curr.next;
  }
  k = k % n;
  while (k++ < n) {
    k === n && (tmp = head);
    head = head.next;
  }
  tmp.next = null;
  return head;
};

/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function(people, limit) {
  if (!people || people.length === 0) {
    return null;
  }
  let count = 0;
  people = people.sort((a, b) => {
    return a - b;
  });
  const len = people.length;
  let left = 0;
  let right = len - 1;
  let res = 0;
  while (left <= right) {
    count++;
    res = people[left] + people[right];
    if (res > limit) {
      right--;
    } else {
      left++;
      right--;
    }
  }
  return count;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
  if (!head) {
    return null;
  }
  var _head = head;
  var current = head;
  var l = 1;
  while (current.next) {
    current = current.next;
    l++;
  }
  var len = l - n;
  if (len == 0) {
    var newHead = head.next;
    head.next = null;
    return newHead;
  }
  if (n == 0) {
    return head;
  }
  current = head;
  var pre = null;
  for (var i = 0; i < len; i++) {
    pre = current;
    current = current.next;
  }
  if (current.next) {
    pre.next = current.next;
    current.next = null;
    return head;
  } else {
    pre.next = null;
    current.next = null;
    return head;
  }
};

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  if (!height || height.length < 3) {
    return null;
  }
  var len = height.length;
  var left = 0;
  var right = len - 1;
  var left_max = 0;
  var right_max = 0;
  var res = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] <= left_max) {
        res += left_max - height[left];
      } else {
        left_max = height[left];
      }
      left++;
    } else {
      if (height[right] <= right_max) {
        res += right_max - height[right];
      } else {
        right_max = height[right];
      }
      right--;
    }
  }

  return res;
};

trap([4, 2, 3]);

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */
/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    if(!head) {
        return null;
    }
    let res = new Node();
    let _head = res, curr = head, hash = new Map();
    while(curr) {
        _head.val = curr.val;
        _head.next = curr.next ? new Node() : null;
        hash.set(curr, _head);
        _head = _head.next;
        curr = curr.next;
    }
    _head = res;
    while(head) {
        _head.random = head.random ? hash.get(head.random) : null;
        _head = _head.next;
        head = head.next;
    }
    return res;
    
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
  var a = headA;
  var b = headB;
  while (a) {
    while (b) {
      if (a == b) {
        return a;
      }
      b = b.next;
    }
    a = a.next;
    b = headB;
  }
  return null;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
  let a = headA;
  let b = headB;
  let hash = new Map();
  while (a) {
    hash.set(a, 1);
    a = a.next;
  }
  while (b) {
    if (hash.has(b)) {
      return b;
    }
    b = b.next;
  }
  return null;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
  var pA = headA;
  var pB = headB;
  while (pA !== pB) {
    pB = pB ? pB.next : headA;
    pA = pA ? pA.next : headB;
  }
  return pA;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
  if (!head) {
    return null;
  }
  var _head = head;
  var current = head;
  var l = 1;
  while (current.next) {
    current = current.next;
    l++;
  }
  var len = l - n;
  if (len == 0) {
    var newHead = head.next;
    head.next = null;
    return newHead;
  }
  if (n == 0) {
    return head;
  }
  current = head;
  var pre = null;
  for (var i = 0; i < len; i++) {
    pre = current;
    current = current.next;
  }
  if (current.next) {
    pre.next = current.next;
    current.next = null;
    return head;
  } else {
    pre.next = null;
    current.next = null;
    return head;
  }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  if (!head) {
    return null;
  }
  var p = head;
  while (p.next) {
    var pre = p.next;
    p.next = p.next.next;
    pre.next = head;
    head = pre;
  }
  return head;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
  if (!head) {
    return null;
  }
  var p = head;
  while (p && p.next) {
    if (p.next.val === val) {
      var q = p.next;
      p.next = p.next.next;
      q.next = null;
      if (p.next == null) {
        break;
      }
    } else {
      p = p.next;
    }
  }
  if (head.val === val) {
    var _head = head;
    head = head.next;
    _head.next = null;
  }
  return head;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
  if (!head) {
    return null;
  }
  if (!head.next) {
    return head;
  }
  var evenHead = head.next;
  var odd = head;
  var even = evenHead;
  head.next = null;
  while (even) {
    var oddNext = even.next;
    if (even.next) {
      even.next = even.next.next;
    }
    if (odd && oddNext) {
      odd.next = oddNext;
      odd = odd.next;
    }
    even = even.next;
  }
  odd.next = evenHead;
  return head;
};

/**
 * Initialize your data structure here.
 */
var Node = function(val) {
  this.val = val;
  this.next = null;
};

var MyLinkedList = function() {
  this.head = new Node(null);
};

/**
 * Get the value of the index-th node in the linked list. If the index is invalid, return -1.
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
  if (!this.head) {
    return -1;
  }
  var p = this.head;
  var i = 0;
  while (p && p.next) {
    if (i == index) {
      return p;
    }
    i++;
    p = p.next;
  }
  return -1;
};

/**
 * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
  var newList = new Node(val);
  if (!this.head) {
    this.head = newList;
    return;
  }
  newList.next = this.head;
  this.head = newList;
};

/**
 * Append a node of value val to the last element of the linked list.
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
  var newList = new Node(val);
  if (!this.head) {
    this.head = newList;
    return;
  }
  var p = this.head;
  while (p.next) {
    p = p.next;
  }
  p.next = newList;
};

/**
 * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
  var newList = new Node(val);
  if (index <= 0) {
    newList.next = this.head;
    this.head = newList;
    console.log("3");
    return this.head;
  }
  var len = 0;
  var p = this.head;
  while (p && p.next) {
    if (len == index) {
      var pNext = p.next;
      p.next = newList;
      newList.next = pNext;
      console.log("5");
      return this.head;
    }
    p = p.next;
    len++;
  }
  console.log("2");
  if (len == index) {
    console.log("1");
    p.next = newList;
    return this.head;
  } else if (len < index) {
    console.log("4");
    return this.head;
  }
};

/**
 * Delete the index-th node in the linked list, if the index is valid.
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

var linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtHead(1);
linkedList.addAtTail(1);
linkedList.addAtIndex(3, 5);
console.log(linkedList);

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  if (!l1 && !l2) {
    return null;
  } else if (!l1 && l2) {
    return l2;
  } else if (l1 && !l2) {
    return l1;
  }
  var head;
  if (l1.val <= l2.val) {
    head = l1;
    l1 = l1.next;
  } else {
    head = l2;
    l2 = l2.next;
  }
  var _head = head;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      head.next = l1;
      head = head.next;
      l1 = l1.next;
    } else {
      head.next = l2;
      head = head.next;
      l2 = l2.next;
    }
  }
  if (l2) {
    head.next = l2;
  }
  if (l1) {
    head.next = l1;
  }
  return _head;
};

function ListNode(val) {
  this.val = val;
  this.next = null;
}

var l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);
var l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);
mergeTwoLists(l1, l2);
// [1,2,4]
// [1,3,4]

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  if (!l1 && !l2) {
    return null;
  }
  var a = 0;
  var num = l1.val + l2.val;
  if (num >= 10) {
    a = 1;
    num = num % 10;
  }
  var head = new ListNode(num);
  var _head = head;
  l1 = l1.next;
  l2 = l2.next;
  if (!l1 && !l2 && a == 1) {
    _head.next = new ListNode(1);
    return _head;
  }
  while (l1 && l2) {
    var l3 = l1.val + l2.val + a;
    a = 0;
    if (l3 >= 10) {
      a = 1;
      l3 = l3 % 10;
    }
    head.next = new ListNode(l3);
    head = head.next;
    l1 = l1.next;
    l2 = l2.next;
  }
  while (l1) {
    l1.val = l1.val + a;
    if (l1.val >= 10) {
      l1.val = l1.val % 10;
    } else {
      a = 0;
    }
    head.next = l1;
    head = head.next;
    l1 = l1.next;
  }
  while (l2) {
    l2.val = l2.val + a;
    if (l2.val >= 10) {
      l2.val = l2.val % 10;
    } else {
      a = 0;
    }
    head.next = l2;
    head = head.next;
    l2 = l2.next;
  }
  if (a == 1) {
    head.next = new ListNode(1);
  }
  return _head;
};

const flatten = (head, next) => {
  let curr = head;
  while (curr && (curr.next || curr.child)) {
    if (curr.child) {
      let res = flatten(curr.child, curr.next);
      let tmp = curr.next;
      curr.next = res;
      curr.child = null;
      curr.next.prev = curr;
      curr = tmp;
    } else {
      curr = curr.next;
    }
  }
  if (next) {
    next.prev = curr;
    curr.next = next;
  }
  return head;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  return root
    ? [root, ...preorderTraversal(root.left), ...preorderTraversal(root.right)]
    : [];
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  var arr = [];
  var res = [];
  root && arr.push(root);
  while (arr.length > 0) {
    var cur = arr.pop();
    res.push(cur.val);
    cur.right && arr.push(cur.right);
    cur.left && arr.push(cur.left);
  }
  return res;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  return root
    ? [...inorderTraversal(root.left), root, ...inorderTraversal(root.right)]
    : [];
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  var result = [];
  var tmpStack = [];
  var currNode = root;
  while (currNode != null || tmpStack.length != 0) {
    while (currNode != null) {
      tmpStack.push(currNode);
      currNode = currNode.left;
    }
    currNode = tmpStack.pop();
    result.push(currNode.val);
    currNode = currNode.right;
  }
  return result;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
  let res = [],
    stack = [];
  while (root || stack.length) {
    res.unshift(root.val);
    if (root.left) stack.push(root.left);
    if (root.right) stack.push(root.right);
    root = stack.pop();
  }
  return res;
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumbers = function(nums) {
  if (!nums || nums.length === 0) {
    return 0;
  }
  var res = 0;
  for (var i = nums.length - 1; i >= 0; i--) {
    if (nums[i].toString().length % 2 === 0) {
      res++;
    }
  }
  return res;
};

findNumbers([12, 345, 2, 6, 7896]);

/**
 * @param {number[][]} points
 * @return {number}
 */
var minTimeToVisitAllPoints = function(points) {
  if (!points || points.length === (0 || 1)) {
    return 0;
  }
  var head = new Node(points[0]);
  var cur = head;
  for (var i = 1, len = points.length; i < len; i++) {
    cur.next = new Node(points[i]);
    cur = cur.next;
  }
  cur = head;
  var res = 0;
  while (cur && cur.next) {
    var nextP = cur.next.val;
    var curP = cur.val;
    var x = Math.abs(nextP[0] - curP[0]);
    var y = Math.abs(nextP[1] - curP[1]);
    var time = Math.abs(x - y) + Math.min(x, y);
    res += time;
    cur = cur.next;
  }
  return res;
};

var Node = function(val) {
  this.val = val;
  this.next = null;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
  if (!root) {
    return null;
  }
  let left = invertTree(root.left);
  let right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
  if (!root) {
    return null;
  }
  let queue = [];
  queue.push(root);
  while (queue.length > 0) {
    let newRoot = queue.shift();
    [newRoot.left, newRoot.right] = [newRoot.right, newRoot.left];
    if (newRoot.left) {
      queue.push(newRoot.left);
    }
    if (newRoot.right) {
      queue.push(newRoot.right);
    }
  }
  return root;
};