数据结构与算法-基础题

动态数组

栈

队列

约瑟夫问题

// 循环链表
function Node(val) {
    this.val = val;
    this.next = null;
}

function create_linkList(n) {
    const head = new Node(1);
    let pre = head;
    for(let i = 2; i <= n; i++) {
        const node = new Node(i);
        pre.next = node;
        pre = node;
    }
    pre.next = head;
    return head;
}

function main() {
    const all = 3;
    const num = 1;

    const list = create_linkList(all);
    let pre = null;
    let cur = list;

    while(cur.next !== cur) {
        for(let i = 0; i < num; i++) {
            pre = cur;
            cur = cur.next;
        }
        pre.next = cur.next;
    }

    console.log(cur.val);
}
main();

链表反转

function reverseList(head) {
    // head 为哨兵节点，不需要反转
    let currentNode = head.next;
    let previousNode = null

    while(currentNode) {
        let nextNode = currentNode.next;

        currentNode.next = previousNode;

        previousNode = currentNode;

        currentNode = nextNode;
    }

    head.next = previousNode;
}

检测链表中的环

function checkCircle(head) {
    let fast = head.next;
    let slow = head;

    while(fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        if(slow === fast) return true;
    }
    return false;
}

链表中间节点

function findMiddleNode() {
    let fast = this.head;
    let slow = this.head;

    while(fast.next && fast.next.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

斐波那契数列

求阶乘

二叉树的遍历

二叉树的高度

归并排序

快速排序

八皇后

背包问题

DFS 的递归代码

二分查找

二分查找变体

堆

堆排序

堆的三种应用（优先级队列、Top k、中位数）

字符串匹配 BF 算法