日界线是指日期的分界线，国际规定180度经线，但这不是一条直线，是一条曲线

先讲个故事，公元1世纪犹太战争，犹太人被包围了，不想被俘虏的“勇士”宁可自杀，首领指着最近的一个说

‘从你开始往后数，数到第三个，他就自杀，再从他下一个开始数，数到第三个自杀，后面的一样，开始吧’

其中聪明的两个人想办法插队，不想就这样死了（其中一个就是约瑟夫）

呵呵这是在告诉我“最困难的一刻，只要去想，总有解决的办法”

来吧，看聪明的ipo怎么解决的

通用的，n个人，第m个自杀，留下的是第几个呢

/*    实例    使用循环链表解决约瑟夫环问题     */    function lastTwo(n, m) {        var list = new LList();        list.insert(1, "head");        for (var i = 2; i <= n; i++) {            list.insert(i, i - 1);        }        var currNode = list.head.next;        var removeNode = null;        while (list.length >= m) {            removeNode = move(currNode, m);            list.remove(removeNode.value);            currNode = removeNode.next;        }        return list.display();    }    function move(currNode, m) {        for (var i = 1; i < m; i++) {            if (currNode.value === 'head') {                i -= 1;            }            currNode = currNode.next;        }        return currNode;    }    lastTwo(3, 3);

实现原理是什么的，慢慢从基础理解

1. 单向链表

   主要阐述了链表是怎么一回事：节点+链

   上代码：

function Node(elem) {//两个类：Node当前节点数据以及下一个节点的引用,LList头节点以及操作链表的方法    this.elem = elem;    this.next = null;}function LList() {    this.head = new Node("head");    this.find = find;    this.findPrevious = findPrevious;    this.insert = insert;    this.remove = remove;    this.display = display;}function find(item) {    var currNode = this.head;    while (currNode.elem !== item) {        currNode = currNode.next;    }    return currNode;}function findPrevious(item) {    var currNode = this.head;    while (currNode.next !== null && currNode.next.elem !== item) {        currNode = currNode.next;    }    return currNode;}function insert(newElem, item) {    var newNode = new Node(newElem);    var currNode = this.find(item);    newNode.next = currNode.next;    currNode.next = newNode;}function remove(item) {    var prevNode = this.findPrevious(item);    if (prevNode.next !== null) {        prevNode.next = prevNode.next.next;    }}function display() {    var currNode = this.head;    while (currNode.next !== null) {        console.log(currNode.next.elem);        currNode = currNode.next;    }}/*创建一个实例 */var cities = new LList();cities.insert("Conway", "head");cities.insert("Russellville", "Conway");cities.display();

今天进行了如下优化，封装，继承

/*        链表=节点+链        节点=节点值+next(节点的引用指向后继)        链=头结点声明初始化+方法+属性         */(function(window) {    function Node(value) {        this.value = value;        this.next = null;    }    var uList = function() {        this.head = new Node("head");        this.length = 0;    };    uList.prototype.find = function(value) {        if (value === "head") {            return this.head;        }        var currNode = this.head.next;        while (currNode !== null) {            if (currNode.value === value) {                return currNode;            } else {                currNode = currNode.next;            }        }        return -1;    };    uList.prototype.insert = function(newValue, currValue) {        var newNode = new Node(newValue);        var currNode = this.find(currValue);        if (currNode !== -1) {            newNode.next = currNode.next;            currNode.next = newNode;        } else {            alert("未找到要插入的位置元素");        }    };    uList.prototype.findPrevious = function(value) {        if (value === "head") {            return -1;        }        var currNode = this.head;        while (currNode.next !== null) {            if (currNode.next.value === value) {                return currNode;            } else {                currNode = currNode.next;            }        }        return -1;    };    uList.prototype.remove = function(value) {        var currNode = this.find(value);        if (currNode !== -1) {            var preNode = this.findPrevious(value);            if (preNode !== -1) {                preNode.next = currNode.next;            } else {                alert("未找到删除的元素");            }        } else {            alert("未找到删除的元素");        }    };    uList.prototype.display = function() {        var currNode = this.head.next;        while (currNode !== null) {            console.log(currNode.value);            currNode = currNode.next;        }    };    var List = function() {        uList.call(List);    };    List.prototype = new uList();    window.List = List;})(window);/*试一下 */var mylist = new List();mylist.insert(1, "head");mylist.display();

单向链表是最简单的链表，JS中把数组搞成对象，性能势必不行了，可以自己造个链表替代数组。不过随机访问一个元素还是数组好些。

• 双向链表

  双向链表比单向链表相比node多了前置引用，方法删除操作修改next的同时要修改pre

function Node(elem){    this.elem=elem;    this.previous=null;    this.next=null;}function LList(){    this.head=new Node("head");    this.find=find;    this.findPrevious=findPrevious;    this.insert=insert;    this.remove=remove;    this.display=display;    this.displayReverse=displayReverse;}function find(elem){    var currNode=this.head;    while(currNode.elem!==elem&&currNode.next!==null){        currNode=currNode.next;    }    return currNode;}function findPrevious(){    var currNode=this.head;    while(currNode.next!==null){        currNode=currNode.next;    }    return currNode;}function insert(newElem,item){    var currNode=this.find(item);    var newNode=new Node(newElem);    if(currNode.next!==null){        currNode.next.previous=newNode;        newNode.next=currNode.next;    }    newNode.previous=currNode;    currNode.next=newNode;}function remove(elem){    var currNode=this.find(elem);    if(currNode.next!==null){        currNode.next.previous=currNode.previous;    }    currNode.previous.next=currNode.next;}function display(){    var currNode=this.head;    while(currNode.next!==null){        console.log(currNode.next.elem);        currNode=currNode.next;    }}function displayReverse(){    var currNode=this.findPrevious();    while(currNode.previous!==null){        console.log(currNode.previous.elem);        currNode=currNode.previous;    }    }

• 循环链表

  循环链表与单向链表相比，强调最后一个节点的引用后继是head，所以初始化链表时头结点时后继是head本身

function Node(elem){    this.elem=elem;    this.next=null;}function LList(){    this.head=new Node("head");    this.head.next=this.head;    this.find=find;    this.insert=insert;    this.findPrevious=findPrevious;    this.remove=remove;    this.display=display;}function find(elem){    var currNode=this.head;    while(currNode.next!==this.head&&currNode.elem!==elem){        currNode=currNode.next;    }    return currNode;}function insert(newElem,item){    var currNode=this.find(item);    var newNode=new Node(newElem);    if(currNode.next!==this.head){        newNode.next=currNode.next;        currNode.next=newNode;    }else{        currNode.next=newNode;        newNode.next=this.head;    }}function findPrevious(elem){    var currNode=this.head;    while(currNode.next.elem!==elem){        currNode=currNode.next;    }    return currNode;}function remove(elem){    var prevNode=this.findPrevious(elem);    var currNode=this.find(elem);    prevNode.next=currNode.next;}function display(){    var currNode=this.head;    while(currNode.next!==this.head){        console.log(currNode.next.elem);        currNode=currNode.next;    }}

优化一下就是文章开头的例子中用到的了

(function(window) {        function Node(value) {            this.value = value;            this.next = null;        }        function list() {            this.head = new Node("head");            this.head.next = this.head;            this.length = 0;        }        list.prototype.find = function(elem) {            if (elem === "head") {                return this.head;            }            var curr = this.head.next;            while (curr !== this.head) {                if (curr.value === elem) {                    return curr;                } else {                    curr = curr.next;                }            }            return -1;        };        list.prototype.insert = function(newValue, currValue) {            var newNode = new Node(newValue);            var currNode = this.find(currValue);            if (currNode === -1) {                alert("未找到插入位置的元素");            } else {                newNode.next = currNode.next;                currNode.next = newNode;                this.length++;            }        };        list.prototype.findPrevious = function(currValue) {            if (this.head.next.value === currValue) {                return this.head;            }            var curr = this.head.next;            while (curr !== this.head) {                if (curr.next.value === currValue) {                    return curr;                } else {                    curr = curr.next;                }            }            return -1;        };        list.prototype.remove = function(elem) {            var curr = this.find(elem);            if (curr === -1) {                alert("找不到要删除的元素");            } else {                var pre = this.findPrevious(elem);                if (pre === -1) {                    alert("找不到要删除的元素");                } else {                    pre.next = curr.next;                    this.length--;                }            }        };        list.prototype.display = function() {            var curr = this.head;            while (curr.next !== this.head) {                console.log(curr.next.value);                curr = curr.next;            }        };        var LList = function() {            list.call(LList);        };        LList.prototype = new list();        window.LList = LList;    })(window);