准备阅读: 《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修饰一样方便。好处在于添加或移动元素时,无需修改其他元素。
对应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] } } }
这个思路没什么好说的。
var removeElements = function(head, val) {
if (head === null) return null
head.next = removeElements(head.next, val)
return head.val === val ? head.next : head
};
性能尚可。
如果用链表的思路呢?
用链表的思路,很容易想到做迭代:
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;
};
运行性能也在一个主流的范围之内。
对应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?
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
易错点在于,如何腾出空间,否则容易陷入内存溢出:
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
};
递归的思路是甩锅,解决不了推给下一代(“搁置争议,交给下一代的智慧去解决”)。
每代的智慧是什么呢?
•遇到尾部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.
性能上要差了很多。
对应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个元素。
对应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;
};
性能:
[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