Js算法与数据结构拾萃（3）：链表
- 2020 年 2 月 25 日
- 筆記
补白
准备阅读： 《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.
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.
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
