个人学习博客

# 链表

# 排序链表

// 用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('==>')
  }
}

//链表反转反复看

← 矩阵 →