NC78反转链表

pre为上一个节点，cur为当前遍历节点，next用来保存下一个节点，每次遍历，先保存下一个节点，让当前节点cur指向它的前一个节点pre，pre和cur同时后移。遍历到最后，cur指向null，pre指向最后一个节点，直接返回pre即可。

function ReverseList(pHead)
{
    let pre = null;
    let cur = pHead;
    let next;
    while(cur){
        next = cur.next;  //保存下一个节点
        cur.next = pre;  //当前指向前一个
        pre = cur;  //pre后移
        cur = next;  //cur后移
    }
    return pre;
}
module.exports = {
    ReverseList : ReverseList
};

NC140排序

由于要求时间复杂度在nlogn，所以写了一个快排。

function MySort( arr ) {
    if( !arr || arr.length < 2) return arr;
    quickSort( arr , 0 , arr.length - 1);
    return arr;
}
function quickSort( arr , l , r){
    if( l > r) return;
    let i = l;
    let j = r;
    let flag = arr[l];
    while( i < j){
        
        while( arr[j] >= flag && i < j){
            j--;
        }
        
        while( arr[i] <= flag && i < j){
            i++;
        }
        
        let temp;
        if(i < j){
            temp  = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[l] = arr[i];
    arr[i] = flag;
    quickSort( arr , l , i - 1);
    quickSort( arr , i + 1 , r)
}
module.exports = {
    MySort : MySort
};

NC93设计LRU缓存结构

这里的key和value一一对应，js里有map数据结构，并且访问时的顺序正是按照set的顺序来。所以我们每次get时，不在map里返回-1到数组answer，若在map里，将结果返回到answer然后delete再重新添加，这样它就在map的前面，当set时发现数量超过k，就删除第一个访问到的，这也是相对于在map结构里最早添加且最近没有被访问的。

function LRU( operators ,  k ) {
    let answer = new Array();
    let map = new Map();
    for( let item of operators ){
        if(item[0] == 1){//set
            if(map.get(item[1])){//原来有 先删除 再添加
                map.delete(item[1]);
                map.set(item[1],item[2]);
            }else{
                map.set(item[1],item[2]);
            }
            if(map.size > k){
                for(let v of map.keys()){
                    map.delete(v);
                    break;
                }
            }
        }else if(item[0] == 2){//get
            let val = map.get( item[1] );
            if(!val){//没找到
                answer.push(-1);
            }else{
                answer.push(val);
                map.delete(item[1]);
                map.set(item[1],val);
            }
        }
    }
    return answer;
}
module.exports = {
    LRU : LRU
};

NC45实现二叉树先中后遍历

递归遍历。

function threeOrders( root ) {
    let arr1 = [];
    let arr2 = [];
    let arr3 = [];
    if(root != null){
        xian(root , arr1);
        zhong(root , arr2);
        hou(root , arr3);
    }
    return [ arr1 , arr2 , arr3 ]
}
function xian(node , arr1){
    arr1.push(node.val);
    if(node.left != null) xian(node.left , arr1);
    if(node.right != null) xian(node.right , arr1);
}
function zhong(node , arr2){
    if(node.left != null) zhong(node.left , arr2);
    arr2.push(node.val);
    if(node.right != null) zhong(node.right , arr2);
}
function hou(node , arr3){
    if(node.left != null) hou(node.left , arr3);
    if(node.right != null) hou(node.right , arr3);
    arr3.push(node.val);
}
module.exports = {
    threeOrders : threeOrders
};

NC119最小的k个数

先快排，然后使用slice方法返回[0,k)个数。

function GetLeastNumbers_Solution(input, k)
{
    quickSort(input , 0 , input.length - 1);
    return input.slice(0,k);
}
function quickSort(input , l , r){
    if( l > r) return ;
    let i = l ;
    let j = r;
    let flag = input[l];
    while(i < j){
        
        while( input[j] >= flag && i < j){
            j--;
        }
        while( input[i] <= flag && i < j){
            i++;
        }
        let temp;
        if( i < j){
            temp = input[i];
            input[i] = input[j];
            input[j] = temp;
        }
    }
    input[l] = input[i];
    input[i] = flag;
    quickSort(input , l , i - 1);
    quickSort(input , i + 1 , r);
}
module.exports = {
    GetLeastNumbers_Solution : GetLeastNumbers_Solution
};

NC15二叉树层序遍历

使用队列层次遍历，只是在每次访问时需要将当前层的节点元素放入同一个数组，记得添加到数组中的是节点的val。

function levelOrder( root ) {
    let ans = [];
    let queue = [root];
    if(root == null) return [];
    while(queue.length != 0){//当队列不为空时
        let each = [];
        let queueLength = queue.length;
        while(queueLength != 0){
            let x = queue.shift();
            each.push(x.val);
            if(x.left != null ) queue.push(x.left);
            if(x.right != null ) queue.push(x.right);
            queueLength--;
        }
        console.log(each)
        ans.push(each);
    }
    return ans;
}
module.exports = {
    levelOrder : levelOrder
};