虽然说算法很复杂，但是在我的工作经验中，掌握这2个基本就够处理大部分前端业务工作（不要跟我抬杠哦，你要面试肯定不够用），所以总结一下~~
快排
const quickSort = l => {
if (l.length < 2) {
return l
}
// 我就把每次数组第一个元素当基点 这样理解简单
let pivot = l[0]
let left = []
let right = []
l.slice(1).forEach(e => {
if (e >= pivot) {
right.push(e)
} else {
left.push(e)
}
})
return quickSort(left)
.concat(pivot)
.concat(quickSort(right))
}
冒泡
// 相邻元素两两对比，元素交换，大的元素交换到后面
const jsSort = l => {
let len = l.length
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (l[j] > l[j + 1]) {
const e = l[j]
l[j] = l[j + 1]
l[j + 1] = e
}
}
}
return l
}
如果为了面试， 你可能需要知道下面这些
class Node {
constructor(x) {
this.element = x
this.next = null
}
}
class LinkedList {
constructor() {
this.head = null
}
length() {
let index = 0
let node = this.head
while (node != null) {
index += 1
node = node.next
}
return index
}
lastNode() {
// 2, 返回单链表的最后一个节点
// 找到最后一个 Node
let n = this.head
while (n != null) {
if (n.next === null) {
return n
}
n = n.next
}
return n
}
kthNode(i) {
// 3, 返回单链表第 i 个节点
let n = this.head
let index = 0
while (n != null) {
if (index + 1 == i) {
return n
}
n = n.next
index++
}
return n
}
nLast(x) {
// 4, 返回单链表倒数第 n 个节点
let len = this.length()
let index = len - x
return this.kthNode(index)
}
hasX(x) {
// 5, 判断单链表中是否有值为 x 的节点
let n = this.head
while (n != null) {
if (n.element == x) {
return true
}
n = n.next
}
return false
}
middle() {
// 6, 查找单链表的中间节点
if (this.length() % 2 === 0) {
return null
} else {
let index = Math.floor(this.length() / 2)
return this.kthNode(index)
}
}
append(e) {
// 7, 给单链表末尾插入一个节点
let node = new Node(e)
// 找到最后一个 Node
let n = this.head
if (n == null) {
this.head = node
} else {
while (n.next != null) {
n = n.next
}
n.next = node
}
return this
}
prepend(x) {
// 8, 给单链表头部插入一个元素
let node = new Node(x)
node.next = this.head
this.head = node
return this
}
insertAfter(n, x) {
// 9, 给单链表第 n 个节点后插入一个元素
let node = new Node(x)
let index = 0
let node2 = this.head
while (n != null) {
if (index == n) {
break
}
node2 = node2.next
index++
}
node.next = node2.next
node2.next = node
return this
}
insertLastN(n, x) {
// 10, 给单链表倒数第 n 个节点前插入一个元素
let nn = this.nLast(n)
if (nn != null) {
if (nn == this.head) {
this.prepend(x)
} else {
let node = new Node(x)
let nn = this.nLast(n + 1)
node.next = nn.next
nn.next = node
}
}
return this
}
deleteN(n) {
// 11, 删除单链表第 n 个节点
if (n == 0) {
let node = this.head
this.head = this.head.next
return node.element
} else {
let node = this.kthNode(n - 1)
if (node != null && node.next) {
let dlete_node = node.next
node.next = node.next.next
return dlete_node.element
}
}
}
deleteX(x) {
// 12, 删除单链表中值为 x 的节点
let n = this.head
if (n && n.element == x) {
return this.deleteN(0)
}
while (n != null) {
if (n.next && n.next.element == x) {
n.next = n.next.next
break
}
n = n.next
}
return this
}
deleteLastN(n) {
// 13, 删除单链表倒数第 n 个节点
let index = this.length() - n
return this.deleteN(index)
}
// 返回反转后的单链表
reverse() {
let node = this.head
let new_node = null
while (node != null && node.next != null) {
new_node = node.next
node.next = new_node.next
new_node.next = this.head
this.head = new_node
}
return this
}
isPalindrome() {
// 15, 判断一个链表是否是回文链表 回文链表自己查加深印象
let new_linked_list = this.reverse()
return JSON.stringify(new_linked_list) == JSON.stringify(this)
}
isCircle() {
// 16, 判断一个链表是否是环形链表 不懂自己查加深印象
// 本题用双指针, a 一次走一格 b 一次走两格，如果相遇说明有环形 这个方法时间空间复杂度是最优解
let slow = this.head
let fast = this.head.next
while (fast && fast.next) {
if (slow == fast) {
return true
}
slow = slow.next
fast = fast.next.next
}
return false
}
copy() {
// 17, 返回一个单链表的复制
let new_linked_list = new LinkedList()
let n = this.head
while (n != null) {
new_linked_list.append(n.element)
n = n.next
}
return new_linked_list
}
powerCopy() {
// 18, 返回一个环形链表的复制
let map = new Map()
let n = this.head
let new_linked_list = new LinkedList()
let index = 0
while (n != null) {
if (map.get(n)) {
break
}
map.set(n, true)
new_linked_list.append(n.element)
n = n.next
index++
}
return new_linked_list
}
_mergeNodeList(l1, l2) {
if (l1 == null) {
return l2
}
if (l2 == null) {
return l1
}
let node
if (l1.element < l2.element) {
node = l1
node.next = this._mergeNodeList(l1.next, l2)
} else {
node = l2
node.next = this._mergeNodeList(l1, l2.next)
}
return node
}
mergeList(linkedList) {
// 19, 合并两个有序链表并保持有序 返回一个新链表
let n1 = this.head
let n2 = linkedList.head
let new_linked_list = new LinkedList()
let nodeList = this._mergeNodeList(n1, n2)
new_linked_list.head = nodeList
return new_linked_list
}
josephList(m) {
// 20, 本题是约瑟夫环问题
// 1, 2, 3 ..., n 这 n 个数字排成一个圆圈 (首尾相连)
// 从数字 1 开始每次从这个圆圈里删除第 m 个数字, 删除后从下一位继续从1开始删除第 m 个数字
// 求出这个圆圈里剩下的最后一个数字
let n = this.head
let index = 1
while (n !== null) {
if (this.head == this.head.next) {
console.log('game over', this)
break
}
if (index == m - 1) {
if (this.head == n.next) {
this.head = n.next.next
}
n.next = n.next.next
n = n.next
index = 1
} else {
n = n.next
index++
}
}
}
rearrange(x) {
// 1 给一个单链表和一个值 x, 对它进行分割, 所有小于x的结点排在大于或等于x的结点之前
let before = new LinkedList()
let after = new LinkedList()
let n = this.head
while (n != null) {
if (n.element < x) {
before.append(n.element)
} else {
after.append(n.element)
}
n = n.next
}
let nn = after.head
while (nn != null) {
before.append(nn.element)
nn = nn.next
}
return before
}
circleHead() {
// 2 给一个链表, 返回环形链表中环形开始的节点, 如果没有环形, 返回 null
let slow = this.head
let fast = this.head.next
while (fast && fast.next) {
if (slow == fast) {
return slow
}
slow = slow.next
fast = fast.next.next
}
return null
}
_findmiddleList(left) {
let n = left
if (n == null || n.next == null) {
return n
}
let slow = left
let fast = left
let slow_next = left
while (fast.next != null && fast.next.next != null) {
slow = slow.next
fast = fast.next.next
slow_next = slow.next
}
slow.next = null
return slow_next
}
_reverse(node) {
// 没有头结点的链表翻转
if (node == null || node.next == null) {
return node
}
let pre = node
let cur = node.next
pre.next = null
while (cur != null) {
let tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
}
return pre
}
reorder() {
// 3
// 给一个链表, 将原链表 L0 -> L1 -> L2 -> ... -> Ln-1 -> ln 排序为
// L0 -> L1 -> Ln -> L2 -> Ln-1 -> ...
// 要求: 不能修改节点的值
let n = this.head
if (n == null || n.next == null) {
return
}
let left = this.head.next
let right = this._findmiddleList(left)
right = this._reverse(right)
// 交替合并
let tmp
while (left != null || right != null) {
if (left != null) {
tmp = left.next
n.next = left
left = tmp
n = n.next
}
if (right != null) {
tmp = right.next
n.next = right
right = tmp
n = n.next
}
}
return this
}
rotateList(k) {
// 4
// 给一个链表, 将列表向右旋转 k 个下标, 其中 k 是非负数
// 例子:
// Input: 1->2->3->4->5->NULL, k = 2
// Output: 4->5->1->2->3->NULL
// Input: 0->1->2->NULL, k = 4
// Output: 2->0->1->NULL
// 其实就是移动
let len = this.length()
let step = k % len
let node = this.nLast(step + 1)
if (node == null) {
return node
}
let n = node.next
node.next = null
let head = this.head
this.head = n
while (n != null && n.next != null) {
n = n.next
}
n.next = head
return this
}
static quickSort(list) {
if (list.length < 2) {
return list
}
let left = []
let right = []
let p = list[0]
for (let i = 1; i < list.length; i++) {
const e = list[i]
if (e < p) {
left.push(e)
} else {
right.push(e)
}
}
return LinkedList.quickSort(left).concat([p]).concat(LinkedList.quickSort(right))
}
_sortmerge(l1, l2) {
let node = new Node(-1)
let n = node
while (l1 != null && l2 != null) {
if (l1.element < l2.element) {
n.next = l1
l1 = l1.next
} else {
n.next = l2
l2 = l2.next
}
n = n.next
}
if (l1) {
n.next = l1
}
if (l2) {
n.next = l2
}
return node.next
}
_sortNodeList(nodeList) {
let head = nodeList
if (head == null || head.next == null) {
return head
}
let pre = head
let slow = head
let fast = head
while (fast && fast.next) {
pre = slow
slow = slow.next
fast = fast.next.next
}
pre.next = null
return this._sortmerge(this._sortNodeList(head), this._sortNodeList(slow))
}
sortList() {
// 给一个链表, 将链表排序
// 要求: 时间复杂度为 O(nlogn)
let n = this.head
let nodeList = this._sortNodeList(n)
this.head = nodeList
return this
}
reverseMn(m, n) {
// 6
// 给一个单链表和正整数 m, n(m < n), 从 m 到 n 开始反转
let start = this.kthNode(m - 1)
let len = n - m
while (len > 0) {
let node = this.kthNode(n - 1)
let end = node.next
node.next = node.next.next
end.next = start.next
start.next = end
start = start.next
len--
}
return this
}
deduplication() {
// 7
// 给一个有序的单链表, 删除所有有重复 value 的节点, 只留下原始列表中不同的 value
let n = this.head
if (n == null || n.next == null) {
return this
}
let value = this.head.element
while (n != null && n.next != null) {
// 重复
if (n.next.element == value) {
n.next = n.next.next
} else {
n = n.next
value = n.element
}
}
return this
}
static addNumber(a, b) {
// 8
// 给两个非空且长度不一定相同的单链表, 表示两个非负整数
// 数字以相反的顺序存储(个位在前), 每个节点都包含一个 value, 将两个 value 相加并返回链表
// 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
// 输出：7 -> 0 -> 8
// 原因：342 + 465 = 807
let num1 = []
let head_a = a.head
while (head_a != null) {
num1.unshift(head_a.element)
head_a = head_a.next
}
let num2 = []
let head_b = b.head
while (head_b != null) {
num2.unshift(head_b.element)
head_b = head_b.next
}
num1 = Number(num1.join(''))
num2 = Number(num2.join(''))
let num = num1 + num2 + ''
num = num.split('')
let new_linked_list = new LinkedList()
let head = new_linked_list.head
num.forEach((i) => {
let tmp = head
head = new Node(Number(i))
head.next = tmp
})
new_linked_list.head = head
return new_linked_list
}
static mergeListK(...args) {
// 9
// 合并 k 个有序链表并保证有序，要求时间复杂度最优，不会就讨论，乱写没价值
// args 是一个包含 k 个链表的数组
if (args.length == 0) {
return null
}
if (args.length == 1) {
return args[0]
}
if (args.length == 2) {
return args[0].mergeList(args[1])
}
let middle = Math.floor(args.length / 2)
let left = args.slice(0, middle)
let right = args.slice(middle)
let l1 = LinkedList.mergeListK(...left)
let l2 = LinkedList.mergeListK(...right)
return l1.mergeList(l2)
}
reverseListK(k) {
// 10
// k 个一组反转链表(25)
// 给一个链表, 以每 k 个为一组来翻转链表
// 例子:
// Given this linked list: 1->2->3->4->5
//
// k = 2, return: 2->1->4->3->5
//
// k = 3, return: 3->2->1->4->5
let head = this.head
if (head == null) {
return this
}
let new_node = new Node(-1)
new_node.next = head
let cur = head
let pre = new_node
let len = this.length()
let num = 0
while (len >= k) {
while (num < k - 1) {
let temp = cur.next
cur.next = temp.next
temp.next = pre.next
pre.next = temp
num++
}
num = 0
pre = cur
cur = cur.next
len -= k
}
this.head = new_node.next
return this
}
}
### 链表 （栈和队列是链表的改良型）
### 队列 （先进先出）
### 栈 （先进后出）
### 哈希表 （Hash table）
### 二叉树 （Binary Tree）