大公司前端面试题(前端面试实录)

导语：前端企业面试题：企业真实案例——28

请实现一个约瑟夫环

首先，你必须先搞清楚什么是约瑟夫环。

相传，在罗马人占领敲他帕特之后，39个犹太人跟约瑟夫以及他的朋友躲到了一个山洞中，39个犹太人决定宁死也不要被敌人抓到，于是决定了一个自杀方式，41个人围成一个圈，由第1个人开始报数，每报数到第3人，该人就必须自杀。然后再由下一个重新报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。他将朋友和自己安排在了第16个和第31个位置，于是逃过了这场死亡游戏。请问他是如何做到的？

它可以衍生为一个通用问题，假设有M个元素

如果把每个人看做一个节点，他们形成了一个单向的循环链表

我们现在假设K=3

当只剩下最后一个元素时

于是我们的核心代码就可以写出来了

while(node.next != node){    1 将指针移动K-1步    2 重新建立连接删除当前节点    3 修正指针位置到下一个}

我们先准备节点类

function Node(name){    this.name = name;    this.next;}

创建一个长度为10的单向循环链表

let head = temp = new Node(1);for(let i=2; i<=10; i++){    temp.next = new Node(i);    temp = temp.next;}temp.next = head;

创建出我们的指针类

function Pointer(node){    this.current = node;    this.move = function(){        this.prev = this.current; //记录前一格        this.current = this.current.next; //当前节点向前移动一格    }}

接下来是完整代码

function Node(name){    this.name = name;    this.next;}function Pointer(node){    this.current = node;    this.move = function(){        this.prev = this.current; //记录前一格        this.current = this.current.next; //当前节点向前移动一格    }}//准备好链表内容let head = temp = new Node(1);for(let i=2; i<=10; i++){    temp.next = new Node(i);    temp = temp.next;}temp.next = head;//创建指针，从head开始var p = new Pointer(head);//设定间隔为3let step = 3;//只要next没有指向元素自身，则循环继续while(p.current != p.current.next){    //指针移动step-1步    for(let i=0; i<step-1; i++){        p.move();    }    //重新建立连接并删除当前元素    p.prev.next = p.current.next;    //修正指针位置到下一个（跟指针move是有区别的）    p.current = p.current.next;}console.log(p.current); //最后一个节点

本文内容由快快网络小蔼创作整理编辑！