跳到主要内容

链表✅

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

  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
}

Open browser consoleTests

单向链表结构实现?​

// 实现链表类，支持如下核心方法
// 节点
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

Open browser consoleTests

合并两个有序链表​

/**
* 合并两个有序链表
* 输入：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

Open browser consoleTests

删除存在重复值的节点​

/**
 * 删除链表中重复的元素
 * 输入：[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

Open browser consoleTests

删除倒数第 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

Open browser consoleTests

翻转链表​

// 反转链表 时间复杂度 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
}

Open browser consoleTests

k 个一组翻转链表​

答案

核心概念 LeetCode 第 25 题（Hard 经典）：给你链表的头节点 head，每 k 个节点一组进行翻转，请你返回修改后的链表。如果节点总数不是 k 的整数倍，那么最后剩余的节点保持原有顺序：

  1. 哨兵节点（Dummy）：设立虚拟头节点 dummy.next = head，统一头区间的翻转边界。
  2. 分组定位：使用指针向前探测 $k$ 步，确认当前组是否满足 $k$ 个节点。若不足直接返回。
  3. 子区间翻转：对当前 $k$ 个节点执行局部迭代反转，并与前驱节点（pre）和后继节点（nextGroup）重新穿针引线。
  4. 推进指针：将 pre 指针移动至翻转后的子链表尾部，继续循环下一组。

代码实现：

function reverseKGroup (head, k) {
  if (!head || k <= 1) return head

  const dummy = { next: head }
  let pre = dummy

  while (true) {
    // 1. 检查剩余节点是否满足 k 个
    let tail = pre
    for (let i = 0; i < k; i++) {
      tail = tail.next
      if (!tail) {
        return dummy.next // 不足 k 个，保持原样结束
      }
    }

    const nextGroup = tail.next
    let cur = pre.next
    let prev = nextGroup

    // 2. 局部翻转 k 个节点
    while (cur !== nextGroup) {
      const temp = cur.next
      cur.next = prev
      prev = cur
      cur = temp
    }

    // 3. 重新拼接：pre 指向翻转后的新头，更新 pre 到新尾
    const newTail = pre.next
    pre.next = tail
    pre = newTail
  }
}

// 复杂度分析
// 时间复杂度：O(n)，每个节点最多被访问和修改指针常数次。
// 空间复杂度：O(1)，严格原地操作。

面试官视角

  • 考查复杂指针操作的边界鲁棒性（不丢指针、断链、成环），使用哨兵节点是代码简洁易读的关键加分项。

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

答案

核心概念 LeetCode 141（环形链表）：判断一个链表中是否有环。

  • 快慢指针法（Floyd 判圈算法）：定义 slow 指针每次走 1 步，fast 指针每次走 2 步。
  • 若链表无环，fast 指针必先到达末尾 null。
  • 若链表有环，fast 指针将在环内不断循环，最终必然与 slow 指针相遇（slow === fast），时间复杂度 $O(n)$，空间复杂度 $O(1)$。

代码实现：

function hasCycle (head) {
  if (!head || !head.next) 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
}
/**
 * 检测链表中的环
 * 通过 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
}

Open browser consoleTests

定位环起点​

答案

核心概念 LeetCode 142（环形链表 II）：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null：

  • 数学证明（相遇与同速相碰）：
    • 设头节点到入环点的距离为 $a$，入环点到首次快慢指针相遇点的距离为 $b$，环的剩余长度为 $c$（环总长 $L = b + c$）。
    • 快指针路程是慢指针的 2 倍：$2(a + b) = a + n(b + c) + b \implies a = (n - 1)(b + c) + c = (n - 1)L + c$。
    • 推论结论：从相遇点出发一个指针，同时从链表头出发另一个指针，两者均每次走 1 步，最终必定在入环点首次相遇！

代码实现：

function detectCycle (head) {
  if (!head || !head.next) return null

  let slow = head
  let fast = head

  // 1. 寻找相遇点
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) {
      // 2. 找到环，将 slow 重置到起点，两者同速推进找环入口
      let ptr = head
      while (ptr !== slow) {
        ptr = ptr.next
        slow = slow.next
      }
      return ptr // 环入口节点
    }
  }

  return null // 无环
}

复杂度分析

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$，无额外哈希表存储。

面试官视角

  • 能否给出快慢指针相遇点与环起点的推导公式是顶级区分度，务必结合数轴距离关系拆解（$a = c$）。

跳表的原理和应用​

  • 原理：

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

  • 应用：

    • 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去重分析了时间