Link 链表

约瑟夫环问题

据说著名犹太历史学家 Josephus有过以下的故事：

在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友（共41个人）躲到一个洞中， 39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式： 41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀， 然后再由下一个重新报数，直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从。 首先从一个人开始，越过k-2个人（因为第一个人已经被越过）， 并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。 这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。 问题是一开始要站在什么地方才能避免自杀？Josephus要他的朋友先假装遵从， 他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

数组下标方案

// 初始状态各坐标都赋值为0，被选中则标记为1
const arr = new Array(41).fill(0)
const key = 3

// 最后会剩下2人，走掉39人
const numOfPeopleToLeave = arr.length - 2

let count = 0
while (arr.filter((checked) => checked === 1).length < numOfPeopleToLeave) {
    for (let i = 0, len = arr.length; i < len; i++) {
        // 如果数组中该坐标已被标记，则直接跳过
        if (arr[i] === 1) {
            continue
        }
        count++
        // 每到第key个人
        if (count === key) {
            // 标记数组中该坐标已被占位
            arr[i] = 1
            count = 0
        }
    }
}
// 输出标记情况，标记为0的表示未被选中，标记为1表示被选中
console.log(arr)

// 输出被留下的人（值为0）对应的坐标
console.log(
    arr
      .map((checked, idx) => checked === 0 ? idx : undefined)
      .filter((idx) => typeof idx === 'number')
)

链表方案（单向循环链表）

如果是单向循环链表的话，对单个链表节点，有：

function Node (next) {
    this.next = next || null
}

每当计数计到3时，将当前node节点的上一个节点的next指向当前node节点的下一个节点， 然后继续从1开始计数，代码就不写了，虽说数据结构上和数组下标方案不同， 逻辑是差不多的，while循环的终止条件可以换成当当前节点next指向null时。

合并2个排序链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

递归版本

function merge(pHead1, pHead2) {
    let node = null;
    if (pHead1 === null) {
        return pHead2;
    } else if (pHead2 === null) {
        return pHead1;
    }

    if (pHead1.val >= pHead2.val) {
        node = pHead2;
        node.next = merge(pHead1, pHead2.next);
    } else {
        node = pHead1;
        node.next = merge(pHead1.next, pHead2);
    }
    return node;
}

非递归版本

function merge(pHead1, pHead2) {
    if (pHead1 === null) {
        return pHead2;
    } else if (pHead2 === null) {
        return pHead1;
    }
    let node = null;
    let startNode = null;
    if (pHead1.val <= pHead2.val) {
        node = pHead1;
        startNode = pHead1;
        pHead1 = pHead1.next;
    } else {
        node = pHead2;
        startNode = pHead2;
        pHead2 = pHead2.next;
    }
    while (pHead1 !== null && pHead2 !== null) {
        if (pHead1.val <= pHead2.val) {
            node.next = pHead1;
            node = pHead1;
            pHead1 = pHead1.next;
        } else {
            node.next = pHead2;
            node = pHead2;
            pHead2 = pHead2.next;
        }
    }
    if (pHead1 !== null) {
        node.next = pHead1;
    } else if (pHead2 !== null) {
        node.next = pHead2;
    }
    return startNode;
}