链表✅

链表设计的核心知识点包括

1. 基本结构
2. 哨兵节点使用
3. 快慢指针
4. 多指针操作

数组转换为链表?

// 实现 arrayToList 函数，将数组转换为链表
// 输入：[1, 2, 3, 4, 5]
// 输出：{ value: 1, next: { value: 2, next: { value: 3, next: { value: 4, next: { value: 5, next: null } } } } }
function arrayToList (arr) {

}

答案

// 数组转换为链表
exports.arrayToLinkList = function arrayToLinkList (arr) {
  // 1. 知道使用哨兵节点，简化边界处理，直接返回 next
  const dummy = { next: null }
  let cur = dummy
  for (let i = 0; i < arr.length; i++) {
    const node = { val: arr[i], next: null }
    cur.next = node
    cur = node
  }
  return dummy.next
}

Tests

单向链表结构实现?

// 实现链表类，支持如下核心方法
// 节点
interface Node {
  value: number
  next: Node | null
}
// 链表
abstract class LinkedList {
  constructor(values: number[]): LinkedList // 构造函数，接收一个数组作为参数，将数组转换为链表
  add(value: any):void // 往链表末尾添加节点
  delete(value: any):void // 删除值为 value 的节点
  deleteValues(values: any[]):void // 批量删除，删除值在 values 数组中的节点
  find(value: any):Node | null // 查找值为 value 的节点
  head:Node | null // 获取链表头节点
  tail:Node | null // 获取链表尾节点
}

答案

/**
 * 该函数用于创建单向链表
 */

class Node {
  constructor (val) {
    this.val = val
    this.next = null
  }
}

class LinkedList {
  _head = null
  _tail = null
  get head () {
    return this._head
  }

  get tail () {
    return this._tail
  }

  constructor (values) {
    // 格式化单个节点或非数组元素为数组
    if (!Array.isArray(values)) {
      values = [values]
    }

    const dummy = { next: null }
    let cur = dummy
    for (let i = 0; i < values.length; i++) {
      const currentNode = new Node(values[i])
      cur.next = currentNode
      cur = currentNode
    }
    this._head = dummy.next
    this._tail = this._head ? cur : this._head
  }

  // 在末尾追加节点
  add (value) {
    const node = new Node(value)
    this._tail.next = node
    this._tail = node
  }

  // 删除值为 value 的节点
  delete (value) {
    const dummy = { next: this.head }
    let cur = dummy
    while (cur) {
      if (cur.next && cur.next.val === value) {
        cur.next = cur.next.next
        break
      }
      cur = cur.next
    }
    this._head = dummy.next
    if (cur.next === null) {
      this._tail = cur
    }
  }

  // 删除所有值为 value 的节点
  deleteValues (values) {
    const dummy = { next: this.head }
    let cur = dummy
    while (cur) {
      if (cur.next && values.includes(cur.next.val)) {
        cur.next = cur.next.next
      } else {
        cur = cur.next
      }
    }
    this._head = dummy.next
    if (!cur?.next) {
      this._tail = cur
    }
  }

  // 返回值为 value 的节点
  find (value) {
    let cur = this.head
    while (cur) {
      if (cur.val === value) {
        return cur
      }
      cur = cur.next
    }
    return null
  }
}

exports.LinkedList = LinkedList
exports.Node = Node

Tests

合并两个有序链表

/**
* 合并两个有序链表
* 输入：l1 = [1,2,4], l2 = [1,3,4]
* 输出：[1,1,2,3,4,4]
 */

function mergeLinkedList (l1, l2) {

}

答案

function mergeLinkList (l1, l2) {
  const dummy = { next: null }
  let current = dummy
  let pl1 = l1
  let pl2 = l2
  while (pl1 && pl2) {
    if (pl1.val < pl2.val) {
      current.next = pl1
      pl1 = pl1.next
    } else {
      current.next = pl2
      pl2 = pl2.next
    }
    current = current.next
  }

  if (pl1) {
    current.next = pl1
  } else {
    current.next = pl2
  }
  return dummy.next
}

module.exports = mergeLinkList

Tests

删除存在重复值的节点

/**
 * 删除链表中重复的元素
 * 输入：[1, 1, 2, 3, 3]
 * 输出：[2, 3]
 */
function removeDuplicate (head) {
}

答案

/**
 * 删除链表中连续重复的节点，只保留不重复的节点
 * @param {ListNode} head - 链表头节点
 * @returns {ListNode} - 处理后的链表头节点
 */
function removeDuplicate (head) {
  const dummy = { next: null }
  let current = dummy
  let pointer = head

  while (pointer) {
    const currentValue = pointer.val

    // 如果下一个节点存在且值相同，跳过所有重复节点
    if (pointer.next && currentValue === pointer.next.val) {
      while (pointer && pointer.val === currentValue) {
        pointer = pointer.next
      }
    } else {
      // 当前节点不重复，保留该节点
      current.next = pointer
      current = pointer
      pointer = pointer.next
    }
  }

  // 处理最后一个节点的next指针
  current.next = null
  return dummy.next
}

module.exports = removeDuplicate

Tests

删除倒数第 n 个节点

/**
 * 删除链表的倒数第 n 个节点
 * 输入：[1, 2, 3, 4, 5], n = 2
 * 输出：[1, 2, 3, 5]
 */
function removeNthFromEnd (head, n) {
}

答案

function removeNthFromEnd (head, n) {
  const dummy = { next: null }
  dummy.next = head
  // 快慢指针
  let first = dummy
  let second = dummy
  if (head === null) return null
  for (let i = 1; i <= n + 1; i++) {
    first = first?.next
  }
  while (first !== null) {
    first = first?.next
    second = second?.next
  }
  second.next = second.next.next
  return dummy.next
}

module.exports = removeNthFromEnd

Tests

翻转链表

// 反转链表 时间复杂度 O(n)，空间复杂度 O(1)
// 输入：[1, 2, 3, 4]
// 输出：[4, 3, 2, 1]
function reverseList (head) {
}

答案

/**
 * 单链表反转
 * 链表结构为 {val:1,next:{val:2,next...}
 * Input: 1->2->3->4->5->NULL
 * Output: 5->4->3->2->1->NULL
 *
 */

module.exports = reverseLinkedList
function reverseLinkedList (list) {
  const values = []
  // 按顺序提取链表的值
  let head = list
  while (head) {
    values.push(head.val)
    head = head.next
  }
  // 重新遍历链表按照相反顺序赋值
  head = list
  while (head) {
    head.val = values.pop()
    head = head.next
  }
  return list
}

Tests

k 接翻转链表

/**
 * K 个一组翻转链表
 * 输入：[1, 2, 3, 4, 5], k = 2
 * 输出：[2, 1, 4, 3, 5]
 */
function reverseKGroup (head, k) {
}

判断单向链表是否是循环链表

/**
 * 判断是否有环
 */
function cycleCheck (head) {
}

答案

/**
 * 检测链表中的环
 * 通过 hash 表判断索引是否被访问
 */

exports.hasCycle = hasCycle
exports.detectCycle = detectCycle

function hasCycle (list) {
  const hashMap = new Map()
  // 按顺序提取链表的值
  let head = list
  while (head) {
    // 若有节点以存在说明发生循环,直接推出
    if (hashMap.has(head)) {
      return true
    } else {
      // 注意此处无需存储链表的值, true 标记节点已访问
      hashMap.set(head, true)
    }
    head = head.next
  }
  // 如果循环推出说明无环
  return false
}

function detectCycle (list) {
  const hashMap = new Map()
  // 按顺序提取链表的值
  let head = list
  while (head) {
    // 若有节点以存在说明发生循环,直接推出
    if (hashMap.has(head)) {
      // 返回索引
      return hashMap.get(head)
    } else {
      // 注意此处无需存储链表的值, true 标记节点已访问
      hashMap.set(head, head)
    }
    head = head.next
  }
  // 如果循环推出说明无环
  return null
}

Tests

判断单向链表是否是循环链表

function isCyclicLinkedList (head) {
  if (!head) {
    return false
  }

  let slow = head
  let fast = head

  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next

    if (slow === fast) {
      return true
    }
  }

  return false
}

定位环起点

跳表的原理和应用

• 原理：

  • 多层链表结构
  • 每层是下层的子集
  • 类似二分查找的思想

• 应用：

  • Redis的有序集合
  • 替代平衡树的场景

• 时间复杂度：平均O(logN)

ugly-num 变体

应该算是一道easy-medium，给定一个数组，只有一个初始数字1，对这个数组的每个数字K，做k*2+1和k*3+1，然后加入数组，要求这个数组是sorted并且没有重复元素，返回第N个这个数组应该是［1,3,4,7,9,10,13，..］
算法
3（1*2+1），4（1*3+1）
7（3*2+1），10（3*3+1）
9（4*2+1）， 13（4*3+1）
因为出现了3算出来的比4还大，所以单纯用queue不行，要用heap，然后用set去重分析了时间