# 链表
# 排序链表
// 用js写一个链表的数据结构
// 声明链表的节点
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, end)
}
}
export {
Node,
NodeList
}
# 删除链表节点(203)
var removeElements = function(head, val) {
let ele = {
next: head
}
let cur = ele
while(cur.next){
if(cur.next.val===val){
cur.next = cur.next.next
}else{
cur = cur.next
}
}
return ele.next
};
# 反转链表(206)
- https://leetcode-cn.com/problems/reverse-linked-list/solution/206-fan-zhuan-lian-biao-by-alexer-660/
- 迭代法
var reverseList = function(head) {
let [prev, cur] = [null, head]
while(cur){
let tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
}
return prev
};
- 尾递归法
var reverseList = function(head) {
return reverse(null, head)
};
function reverse(prev, cur){
if(!cur) return prev
let tmp = cur.next
cur.next = prev
return reverse(cur, tmp)
}
- 递归
var reverseList = function(head) {
if(!head||!head.next) return head
let next = head.next
let reverseHead = reverseList(next)
head.next = null
next.next = head
return reverseHead
};
var reverseList = function(head) {
// 如果测试用例只有一个节点 或者 递归到了尾节点,返回当前节点
if(!head || !head.next) return head;
// 存储当前节点的下一个节点
let next = head.next;
let reverseHead = reverseList(next);
// 断开 head ,如图闪电⚡️标记处
head.next = null;
// 反转,后一个节点连接当前节点
next.next = head;
return reverseHead;
};
# 环形链表(141)
- 哈希表
var hasCycle = function(head) {
let map = new Map()
while(head!==null){
if(map.has(head)){
return true
}
map.set(head, true)
head = head.next
}
return false
};
- 快慢指针
var hasCycle = function(head) {
let slow = head
let fast = head
while(fast && fast.next){
slow = slow.next
fast = fast.next.next
if(slow === fast){
return true
}
}
return false
};
# 链表入环点(142)
var detectCycle = function (head) {
let slowP = head, fastP = head // 都从头节点出发
while (fastP) { // head就是null了,没有入环点,直接返回null
if (fastP.next == null) return null // fastP.next为null也说明无环
slowP = slowP.next // 慢指针走一步
fastP = fastP.next.next // 快指针走两步
if (slowP == fastP) { // 首次相遇
fastP = head // 让快指针回到头节点
while (true) { // 开启循环,让快慢指针相遇
if (slowP == fastP) { // 相遇,地点发生在入环处
return slowP // 返回出指针的位置
}
fastP = fastP.next // 快慢指针都走一步
slowP = slowP.next
}
}
}
return null
};
# 链表
class Node{
constructor(element){
this.ele = element;
this.next = null
}
}
class LinkNodeList{
constructor(){
this.head = null;
this.length = 0;
}
append(ele){
let node = new Node(ele)
let cur
if(this.head==null){
this.head = node
}else{
cur = this.head
while(cur.next){
cur = cur.next
}
cur.next = node
}
this.length++
}
toString(){
let cur = this.head
let ret = [];
while(cur){
ret.push(cur.ele)
cur = cur.next
}
return ret.join('==>')
}
}
//链表反转反复看