共 7 篇文章

Js算法与数据结构拾萃（4）：二叉树

Js算法与数据结构拾萃（5）：二分法

Js算法与数据结构拾萃（6）：回溯

Js算法与数据结构拾萃（6.5）：回溯法解决数独问题

清单首页Js算法与数据结构拾萃系列文章详情

清单「Js算法与数据结构拾萃系列」 03/07

Js算法与数据结构拾萃（3）：链表

一粒小麦·首席背锅工程师

Js算法与数据结构拾萃（3）：链表

补白

准备阅读：《javascript数据结构和算法》读书笔记：链表

这仍然是笔者一年前的笔记。

对于一个数组，想要做篡改是复杂度是非常高的，设想你接到一个需求，让你记录存储一个人的简历，你用数组储存，可能是这样的：

resume=['克莱登大学','三闾大学']

如果你想增删改，比如：

// 第1个位置插入点金银行
resume.splice(1, 0, '点金银行'); 

// 删除克莱登大学
resume.splice(0,1)

// 修改
arr[1]='三闾大学';

这时考虑使用一个不连续的内存储存结构来降低复杂度。

链表储存有序的元素集合，但不同于数组，链表元素的内存不是连续放置的。每个元素包括：

•元素本身•指向下个元素的引用。

链表在js中同样也是没有定义的，需要的话得自己创建一个（LinkList）：

class LinkList{
    constructor(){
        // 定义生成节点的工厂方法
        this.Node=function(ele){
            // 元素本身
            this.ele=ele;
            // 地址指针
            this.next=null;
        }

        this.length=0;
        this.head=null;
    }

    /**
     * 在链表尾部追加节点
     * @param {*} ele 
     */
    append(ele){
        // 如果链表为空（head为0，赋值node给head，
        // 否则，根据索引值next找到最后一项）
        const node=new this.Node(ele);
        let current=null;
        if(this.head==null){
            this.head=node;
        }else{
            current=this.head;
            while(current.next){
                current=current.next
            }
            current.next=node;
        }
        this.length+=1;
    }

    /**
     * insert:在指定位置插入节点
     * @param {number} pos 
     * @param {*} ele 
     */
    insert(pos,ele){
        // 如果在链表范围内，
        if(pos>-1 && pos<this.length){
            const node= new this.Node(ele);
            let current=this.head;
            let pre=null;
            let index=0;
            if(pos==0){
                node.next=this.head;
                this.head=node;
            }else{
                // 一路寻找指针为pos的节点
                // 找到后：
                // 把上个节点的指针指向node
                // 把node的指针指向当前节点
                while (index++<pos) {
                    pre=current;
                    current=current.next;
                }
                node.next=current;
                pre.next=node;
            }

            this.length++;
            return true;
        }else{
            // 插入位置超出链表范围
            return false;
        }
    }

    /**
     * 移除指定位置的节点并返回
     * @param {number} pos 
     */
    removeAt(pos){
        if(pos>-1&& pos<this.length){
            let current=this.head;
            let pre=null;
            let index=0;
            if(pos==0){  
                // 移除第一项,把头部之后的节点赋值给头部。即可！
                this.head=current.next;
            }else{
                while(index++<pos){
                    pre=current;
                    current=current.next;
                }

                pre.next=current.next;
            }

            this.length-=1;
            return current.ele;
        }
    }

    /**
     * 返回指定元素的索引
     * @param {*} ele 
     */
    indexOf(ele){
        let current=this.head;
        let index=0;
        while (current) {
            if(ele==current.ele){
                return index;
            }
            index++;
            current=current.next;
        }

        return -1;
    }

    /**
     * 删除指定元素
     * @param {*} ele 
     */
    remove(ele){
        const index=this.indexOf(ele);
        return this.removeAt(index);
    }

    /**
     * 返回长度
     */
    size(){
        return this.length;
    }

    /**
     * 是否为空
     */
    isEmpty(){
        return this.length==0;
    }

    /**
     * 打印链表方法：输出链表的元素值
     */
    toString(){
        let current=this.head;
        let string='';

        while (current) {
            string+=current.ele+(current.next?'->':'');
            current=current.next;
        }

        return string;
    }

    /**
     * 获取头部
     */
    getHead(){
        return this.head;
    }

    /**
     * 获取尾节点
     */
    getTail(){
        let current=this.head;
        while(current.next){
            current=current.next;
        }
        return current.ele;
    }

}

/** 测试用例 **/ 
// 定义列表
let resume=new LinkList();
resume.append('克莱登大学');
resume.append('三闾大学');
console.log(resume.toString())

// 插入节点
resume.insert(1,'点金银行');
console.log(resume.toString())

// 删除节点
resume.removeAt(0)
console.log(resume.toString())

相对于传统的数组，链表是一个真正动态数据结构。遍历的核心在于一个while循环：

let current=this.head;
while(condition){
    current=current.next;
}

基本方法封装做好后，它的编辑就像DNA修饰一样方便。好处在于添加或移动元素时，无需修改其他元素。

【案例1】Remove Linked List Elements 移除链表元素

对应leetcode第203题难度：简单 https://leetcode.com/problems/remove-linked-list-elements/submissions/

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2-3->4->5

首先要明确这里给出的JavaScript链表形式是怎样的,以测试用例1->2->6->3->4->5->6举例：

ListNode {
  val: 1,
  next:
   ListNode { val: 2, next: ListNode { val: 6, next: [ListNode] } } }

题解1:递归

这个思路没什么好说的。

var removeElements = function(head, val) {
    if (head === null) return null
    head.next = removeElements(head.next, val)
    return head.val === val ? head.next : head
};

性能尚可。

如果用链表的思路呢？

题解2:链表迭代

用链表的思路，很容易想到做迭代：

var removeElements = function(head, val) {
        let current=head;
        let pre=null;

        if(!head){
            return head;
        }

        while(current){
            if(current.val==val){
                pre.next=current.next;
            }
            pre=current;
            current=current.next;
        }

        return head;
};

然而不行。当测试用例为1->2，1或1，1时头部判断会报错。也就是说，当由目标值val开头，无论怎样都会少算。

设想我们把head作为一个新链表的next，这个新链表就回避了开头的问题。

以通过哨兵节点去解决它，哨兵节点广泛应用于树和链表中，如伪头、伪尾、标记等，它们是纯功能的，通常不保存任何数据，其主要目的是使链表标准化，如使链表永不为空、永不无头、简化插入和删除。

var removeElements = function(head, val) {
        let current=head;
        let node={val:null,next:head};
        let pre=node;

        while(current){
            if(current.val==val){
                pre.next=current.next;
            }else{
                pre=current;
            }
            current=current.next;
        }

        return node.next;
};

运行性能也在一个主流的范围之内。

【案例2】Reverse Linked List 反转链表

对应leetcode第206题难度：简单 https://leetcode.com/problems/reverse-linked-list/

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

题解1:迭代

易错点在于，如何腾出空间，否则容易陷入内存溢出：

var reverseList = function(head) {
    let current=head;
    let pre=null;

    while(current){   
        // 缓存next
        let next=current.next;
        // 调换箭头
        current.next=pre;
          // 从缓存取current.next
        pre=current;
        current=next;
    }

    return pre
};

题解2:递归

递归的思路是甩锅，解决不了推给下一代（“搁置争议，交给下一代的智慧去解决”）。

每代的智慧是什么呢？

•遇到尾部next为null，递归终止•遇到头部，让它的next为空。•不断将 next 放入递归方法反转链表，结果next = 当前节点. （Tip: 推进结果直到 next.next 为空）

var reverseList = function(head,pre) {
    if(!head || !head.next)  return head;
    let next=head.next;

    let ret=reverseList(next);
    head.next=null;
    next.next=head;

    return ret;
};

复杂度分析:

•时间: O(n). 等同于正常推进，故 O(n).•空间: O(1). 尾递归方式，重复使用一个空间故空间复杂度为 O(1).

执行结果：

Runtime: 64 ms, faster than 43.25% of JavaScript online submissions for Reverse Linked List.

Memory Usage: 35.3 MB, less than 32.61% of JavaScript online submissions for Reverse Linked List.

性能上要差了很多。

【案例3】Linked List Cycle 环形链表

对应leetcode第141题难度：简单 https://leetcode.com/problems/linked-list-cycle/

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

你能用O(1)内存解决此问题吗？

链表尾连接到链表中的位置为pos，遍历的逻辑就不好使了。

题解一：快慢指针

设想链表是一条跑道，跑道上进行一场龟兔赛跑。乌龟必须一步一步走，兔子可以跳，那么，如果跑道不是环形，兔子将首先冲过跑道终点。这时可判断为false。跑道如果成环形，龟兔始终会再次相遇（套圈），那返回true。

var hasCycle = function(head) {
    let fast=head;
    let slow=head;

    if(head==null){ return false; }

    while(fast!=null && fast.next!==null){
        fast=fast.next.next;
        slow=slow.next;

        if(fast==slow){
            return true;
        }

    }

    return false
};

时间复杂度：O(n)，让我们将 n设为链表中结点的总数。为了分析时间复杂度，我们分别考虑下面两种情况。

•链表中不存在环：快指针将会首先到达尾部，其时间取决于列表的长度，也就是 O(n)。•链表中存在环：我们将慢指针的移动过程划分为两个阶段：非环部分与环形部分：•慢指针在走完非环部分阶段后将进入环形部分：此时，快指针已经进入环中迭代次数 = 非环部分长度 = N迭代次数= 非环部分长度=N•两个指针都在环形区域中：考虑两个在环形赛道上的运动员 - 快跑者每次移动两步而慢跑者每次只移动一步。其速度的差值为 1，因此需要经过二者之间距离/速度差值次循环后，兔子可套圈乌龟，假设环状长度为K，因此，在最糟糕的情形下，时间复杂度为 O(N+K)，也就是 O(n)。

我们只使用了慢指针和快指针两个结点，所以空间复杂度为 O(1)。

题解二：哈希表

回想《Js算法与数据结构拾萃（1）[1]》中两数之和的相亲party问题。我们将场景稍微改一下：你组织一群单身青年参加一场天使与国王的游戏，但是抽签结果中出现了“套圈”的情形（A的国王是B，B的国王是C，C的国王是A），这时候你会怎么判断出来？

最直接的想法就是：到场签到时要求每个人告诉你，自己的国王是谁。由你写在记录本(集合中)上。如果发现某人的国王在签到名单中出现，那么就可以判套圈。

js已经支持了Set数据类型。这是个好消息。

var hasCycle = function(head) {
    let book=new Set([]);

    while(head!=null){
        if(book.has(head)){
            return true;
        }else{
            book.add(head);
        }
        head=head.next
    }

    return false;
};

这种解法相信更直观些。但是空间复杂度为O(n)

时间复杂度：O(n)，对于含有 n 个元素的链表，我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(1)时间。

空间复杂度：O(n)，空间取决于添加到哈希表中的元素数目，最多可以添加 n个元素。

【案例4】Linked List Cycle 环形链表

对应leetcode第142题难度：中等 https://leetcode.com/problems/linked-list-cycle-ii/

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow-up: Can you solve it without using extra space?能否不使用额外空间解决

题解：引入第三个指针

在此不考虑哈希表方法，依然用龟兔赛跑为例子

•阶段1:用双指针判断当前为环形链表，快慢指针必定在环内相遇：•阶段2:如果是环形链表—>直接在head设定第三根指针，速度和fast一致，那么当它们相遇时，必定是链表的交叉路口。

阶段2的论证：

给定阶段 1 找到的相遇点，阶段 2 将找到环的入口。首先我们初始化额外的两个指针：cur，指向链表的头，此时fast指向相遇点。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口，返回这个节点。

下面的图将更好的帮助理解和证明这个方法的正确性。

我们仍然以龟兔赛跑为例子：假设兔子在环上追上乌龟的地点是first。那么，乌龟走的距离为F+a。相同时间，兔子走了F+a+b（全程，完成至少一圈，套圈次数大于1时可不计）后，再走了a的距离才追上乌龟。

因此，新指针cur和兔子必定在同速度走完F的路程后在路口相遇。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let fast=head;
    let slow=head;

    if(head==null){ return null; }

    while(fast!=null && fast.next!==null){
        fast=fast.next.next;
        slow=slow.next;

        if(fast==slow){
            // 有环
            let cur=head;
            while(cur!==fast){
                fast=fast.next;
                cur=cur.next;
            }

            return cur;

        }

    }

    return null;
};

性能：

References

[1] Js算法与数据结构拾萃（1）: http://mp.weixin.qq.com/s?__biz=MzIxMDQ2NjUwNg==&mid=2247484382&idx=1&sn=17002179d2b92645c6f5b4b1084a5721&chksm=9765607ba012e96d4a48894314b871f2074ec8b1dab86f42690de1648b9d3c0e7c568d4585d5&token=1920855520&lang=zh_CN#rd

Js算法与数据结构拾萃系列