数据结构之链表
- 知识点
如何手动地创建一个链表的数据结构(NodeList)
知道链表如何排序(sort)
如何检测链表是否是闭环的 - 概念
链表由一系列结点（元素）组成，结点可以在运行时动态生成。每个结点包括两个部分：存储数据元素的数据域和存储下一个结点地址的指针域。
链表只暴露一个头指针，后面的元素必须通过头指针不断的next，才能拿到 - js中没有链表结构
数组可以充当队列，可以充当堆栈，但是不能充当链表
排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
什么是快速排序？
选择一个基准值，小于的放它左边，大于的放它右边，然后左边右边再选一个基准值，以此类推。
定义两个指针，q指针遍历所有链表节点，如果q指针指向的元素小于基准元素，就和p指针的后一个元素进行交换，同时p后移一位。最后让基准元素和小于它的后一个元素进行交换
// 声明链表的节点
class Node {
constructor(value) {
this.val = value;
this.next = undefined
}
}
// 声明链表的数据结构
class NodeList {
constructor(arr) {
// 声明链表的头部节点
let head = new Node(arr.shift())
let next = head
arr.forEach(item => {
next.next = new Node(item)
next = next.next
})
return head
}
}
// 交换两个节点的值
let swap = (p, q) => {
let val = p.val
p.val = q.val
q.val = val
}
// 寻找基准元素的节点
let partion = (begin, end) => {
let val = begin.val
let p = begin
let q = begin.next
while (q !== end) {
if (q.val < val) {
p = p.next
swap(p, q)
}
q = q.next
}
// 让基准元素跑到中间去
swap(p, begin)
return p
}
export default function sort(begin, end) {
if (begin !== end) {
let part = partion(begin, end)
sort(begin, part)
sort(part.next, end)
}
}
export {
Node,
NodeList
}
// 拿到头指针
let head =new NodeList([4,1,3,2,7,9,10,12,6])
// 对头指针进行排序
sort(head)
let res=[]
let next=head
while(next){
res.push(next.val)
next=next.next
}
console.log(res)// [1,2,3,4,6,7,9,10,12]
const merge = (l, r) => {
let result = new ListNode('sb');
let current = result;
while(l && r) {
if(l.val < r.val) {
current.next = l;
l = l.next;
current = current.next;
} else {
current.next = r;
r = r.next;
current = current.next;
}
}
current.next = l || r;
return result.next;
}
// 归并排序
var sortList = function(head) {
if(head === null || head.next === null) return head;
let fast = head;
let slow = head;
while(fast.next && fast.next.next) {
fast = fast.next.next;
slow = slow.next;
}
const mid = slow.next;
slow.next = null;
return merge(sortList(head), sortList(mid));
};
环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
- 环形检测原理
两个指针一个快，一个慢，同时出发。快的和慢的相遇
快的在慢的后面
// 声明链表的节点
class Node {
constructor(value) {
this.val = value;
this.next = undefined
}
}
// 声明链表的数据结构
class NodeList {
constructor(arr) {
// 声明链表的头部节点
let head = new Node(arr.shift())
let next = head
arr.forEach(item => {
next.next = new Node(item)
next = next.next
})
return head
}
}
export default function isCircle(head) {
// 慢指针
let slow = head
// 快指针
let fast = head.next
while (1) {
if (!fast || !fast.next) {
return false
} else if (fast === slow || fast.next === slow) {
return true
} else {
slow = slow.next
fast = fast.next.next
}
}
}
export {
Node,
NodeList
}
// 检测
let head=new NodeList([6,1,2,5,7,9])
// 设置环状
head.next.next.next.next.next.next=head.next
console.log(isCircle(head))// true
