链表 - kscarrot/blog GitHub Wiki
单向链表和双向链表的区别来自于节点的结构不同.
//单向链表节点
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
//双向链表节点
class Node {
constructor(value) {
this.value = value
this.prev = null
this.next = null
}
}单向链表只能从当前节点,访问下一个节点 双向链表可以从当前节点,同时访问下一个节点和上一个节点
头指针一般作为链表的入口,尾指针和链表长度方便使用,非必须.
将 node ->插入ab之间 -> a -> b ->
const b = a.next
node.next = b // node -> b
a.next = node // a -> node
// -> a -> node -> b ->将 <- node ->插入ab之间 <-> a <-> b <->
const b = a.next
a.next = node // a -> node
node.prev = a // a <-> node
b.prev = node // node <- b
node.next = b // node <-> b
// <-> a <-> node <-> b <->将 -> a -> b -> c ->中的 b删除
const c = b.next
a.next = c // -> a -> c ->
b.next = null // b -> c -> |=> b -> null将 <-> a <-> b <-> c <->中的 b删除
const a = b.prev
const c = b.next
a.next = c // <-> a -> c <->
c.prev = a // <-> a <-> c <->
b.next = null // a <- b -> c |=> a <- b -> null
b.prev = null // a <- b -> null |=> null <- b -> null- 在头部插入
head -> new node,new node.prev = null - 在尾部插入
tail -> new node,new node.next = null - 在头部删除
head -> delete node.next - 在尾部删除
tail -> delete node.prev - 在空链表插入
index = 0 && length = 0同时触发头部和尾部的插入 - 在单个元素的链表删除
index = 0 && length = 1同时触发头部和尾部的删除
将普通链表的头尾结点连接起来,就形成了一个循环链表
循环链表需要一个"头"作为环的入口,实际上无头无尾.
List.length是一个可选项,可以由两个指针等值比较计算出来.
getLength() {
if (!this.head) {
return 0
}
let length = 1
const start = this.head
let point = this.head
while (point.next !== start) {
point = point.next
length++
}
return length
}一些性质:
- 单链表必须从头结点开始才能遍历整个链表;循环单链表可以从任何元素开始
- 不加限制的重复访问下一个节点会死循环
- 元素位置可以大于环上节点个数,最后访问到的节点为
index % List.length - 头节点可以指向环上任何一个节点
如果把一个普通链表的尾部和一个循环链表的头部接起来,那么就在链表里构造了一个环. 另一种构造方式:把一个普通链表的尾部和链表非头部节点接起来,也在链表里构造了一个环. 带环的链表可以想象成"9"的形状,分为两个部分:环(0),直链(1)
-
如何判断一个链表是否有环 LC141:Linked List Cycle: 快慢指针,相遇则有环
-
如何找出环的入口 LC142:Linked List Cycle II: 判断有环,相遇时让新指针
point从头开始向后遍历,point与慢指针slow再次相遇即为入口节点
简单证明:
设直链长为s,环周长为r,慢指针总步数为l,慢指针在环内走过的距离为x
慢指针 :l = s + x [1]
快指针 :2l = s + x + k*r k>=1 [2]
[1]代入[2] 即: k*r = s + x
慢指针在环内走过x,然后再通过point走s,正好走了k整圈,相遇点则为环的入口
- 大部分题目都是单链表
- 常规题使用map建索引,再转换成数组进行操作,可以暴力解决大部分问题,但是违背练习链表题的初衷;更加粗暴的方法是,遍历之后用数组进行操作,再重新建一条链表,这在节点开销大的时候基本上是不能接受的
- 在开头部分,对空链表,长为1的链表等特殊情况直接进行判断可以简化后续的操作逻辑
- 当你需要使用当前遍历节点的前一个节点的时候,最好建一个头结点,使用双指针移动的方式可以拿到当前节点和前一个节点,这个在题目普遍为单链表的时候有利于简化代码.另外,在返回结果的时候还可以利用头节点返回链表的头.
- 涉及到拼接/删除的问题最好画出草图,然后再写代码会更加清晰
删除排序链表中的重复元素 回顾一下如何删除一个节点,判断是否需要删除,需要就直接往后指就行了.
var deleteDuplicates = function (head) {
if (!head) return null
let p = head
while (p.next) {
if (p.next.val === p.val) {
p.next = p.next.next
} else {
p = p.next
}
}
return head
}利用双指针,快指针先走n格,然后同时向后遍历,当快指针到链表尾部的时候,慢指针正好走到倒数第n个
var removeNthFromEnd = function (head, n) {
let fast = head
for (let i = 1; i <= n - 1; i++) {
fast = fast.next
}
let slow = head
let prev = null
while (fast.next) {
prev = slow
fast = fast.next
slow = slow.next
}
if (prev === null) {
return slow.next
} else {
prev.next = slow.next
}
return head
}同样是双指针的思路,快指针每次走两格,慢指针每次走一个,当快指针到链表尾部的时候,慢指针正好走到链表的中点.
var middleNode = function (head) {
let slow = head
let fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
}
return slow
}反转链表
非常经典的题目,存三个指针,pre,cur,next.
cur -> pre,这样就完成了反转,接着依次向后移动就行了,这里经常涉及到什么时候的结束的问题,这个比较灵活,我通常是先跑然后debug.
var reverseList = function (head) {
if (!head) return null
let cur = head.next
let pre = head
pre.next = null
while (cur) {
let temp = cur.next
cur.next = pre
pre = cur
cur = temp
}
return pre
}结合找第n接结点加反转链表的题目.
回文链表 单纯要ac的话,遍历一边用数组判断是比较好解决的. 不额外开空间,就需要在链表上原地操作. 这题其实就是,找中点,然后结合反转链表II把中点后的部分反转,接着从头和中点向后对比两个链表部分是否相等即可.