算法与数据结构 ​

function quickSort (arr) {
  const res = (arr) => {
    if (arr.length <= 1) { return arr; }
    const left = [];
    const right = [];
    const mid = arr[0]; // 基准元素
    for (let i = 1; i < arr.length; i++){
      if (arr[i] < mid) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return [...res(left), mid, ...res(right)]
  }
  return res(arr)
};

console.log(quickSort([5, 6, 1, 3, 10, 2, 9, 4]));

const detectCycle = function(head) {
  if(!head || !head.next) return false;
  let slow = head;
  let fast = head.next;
  while(slow !== fast) {
      if(!fast || !fast.next) return false;
      slow = slow.next;
      fast = fast.next.next;
  }
  return true;
};

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

let reverseList = (head) => {
    if(!head) return null;
    let pre = null, cur = head;
    while(cur) {
        //关键：保存下一个节点的值
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

const reverseBetween = function(head, m, n) {
  let count = n - m;
  let p = dummyHead = new ListNode();
  let pre, cur, front, tail;
  p.next = head;
  for(let i = 0; i < m-1; i++){
      p = p.next;
  }
  //保存前节点
  front = p;
  //同时保存区间首节点
  pre = tail = p.next;
  cur = pre.next;
  //区间反转
  for(let i = 0; i < count; i++) {
      let next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
  }
  //前节点的next指向区间末尾
  front.next = pre;
  //区间首节点的next指向后节点（循环完后的cur就是区间后面第一个节点，即后节点）
  tail.next = cur;
  return dummyHead.next;
}

const levelOrder = function(root) {
  let res = [], queue = [] //存储节点的队列queue
  queue.push(root); //将二叉树根节点入队列
  if(root === null) return res;
  while(queue.length !== 0){
      let length = queue.length; //获取当前队列长度
      let curLevel = []; //存储当前层节点的值
      for(let i=0; i < length; i++){ //遍历当前层的所有节点
          let node = queue.shift(); //从队列中取出一个节点
          curLevel.push(node.val); //将该节点的值存入curLevel数组
          node.left && queue.push(node.left); //如果该节点有左子节点，将其加入队列
          node.right && queue.push(node.right); //如果该节点有右子节点，将其加入队列
      }
      res.push(curLevel); //将当前层的节点值数组curLevel存入结果数组res中
  }
  return res;
};

const preorderTraversal = function(root) {
  let res = [];
  const dfs = function(root){
      if(root===null) return;
      res.push(root.val);//先序遍历所以从父节点开始
      dfs(root.left);//递归左子树
      dfs(root.right);//递归右子树
  }
  //只使用一个参数 使用闭包进行存储结果
  dfs(root);
  return res;
};

const inorderTraversal = function(root) {
  let res = [];
  const dfs = function(root){
      if(root===null) return;
      dfs(root.left);
      res.push(root.val);
      dfs(root.right);
  }
  dfs(root);
  return res;
};

const postorderTraversal = function(root) {
  let res = [];
  const dfs = function(root){
      if(root===null) return;
      dfs(root.left);
      dfs(root.right);
      res.push(root.val);
  }
  dfs(root);
  return res;
};