链表 | 前端小枫

链表是我们在大学课程中必学的一种数据结构，它通过指针将所有的结点连接起来，在 javascript 中我们通常使用对象来实现链表，一个结点的构造函数长这样

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

一个完整的链表结构如下所示

基础链表操作

链表在一般的考核中主要涉及结点的增删改查，我们将以下面这个链表来进行基本的链表操作演示。

const node1 = new ListNode(1)
const node2 = new ListNode(3)
const node3 = new ListNode(5)
const node4 = new ListNode(11)
const node5 = new ListNode(23)

node4.next = node5
node3.next = node4
node2.next = node3
node1.next = node2

/**
 * @description: 遍历链表
 * @param {ListNode} head
 * @return {string}
 */
function linkedListToString(head) {
  let cur = head
  let str = ''
  while (cur) {
    str += `val: ${cur.val}|next =>`
    cur = cur.next
  }
  return str + 'null'
}

console.log(linkedListToString(node1));
// val: 1|next =>val: 3|next =>val: 5|next =>val: 11|next =>val: 23|next =>null

查找结点

查找结点的过程相对简单，通过循环不断地遍历列表来查找符合要求的结点

例如，统计链表中数值大于10 的结点数

/**
 * @description: 统计大于某个值的结点数
 * @param {number} n
 * @return {number}
 */
function countMoreThan(n) {
  let cur = node1
  let cnt = 0

  while (cur) {
    if (cur.val > n)
      cnt++
    cur = cur.next
  }
  return cnt
}
console.log(countMoreThan(10));

查找链表的过程就是不断地通过 next 指针来推进链表

增加结点

增加一个结点需要做的事情是将要插入位置的两侧通过指针操作关联起来，如下图所示

通过这个例子来说明一下具体操作：在有序链表中正确的位置插入一个新的结点，数值为 6

/**
 * @description: 向链表中添加新的结点
 * @param {ListNode} oldList 原来的链表
 * @param {ListNode} newNode 要插入的结点
 * @return {void}
 */
function addNode(oldList, newNode) {
  let cur = oldList
  while (cur.next) {
    if (cur.val < newNode.val && cur.next.val > newNode.val) {
      newNode.next = cur.next
      cur.next = newNode
      break
    }
    cur = cur.next
  }
}
let newNode = new ListNode(6)
addNode(node1, newNode)
console.log(linkedListToString(node1));
// val: 1|next =>val: 3|next =>val: 5|next =>val: 6|next =>val: 11|next =>val: 23|next =>null

要注意操作链表的顺序，一定要先把后置位的元素添加到新元素之后，如果先把新元素赋值前置位的 next，后续的结点就会丢失

删除结点

删除节点的操作更为简单，只需要将要删除结点的 next 指针赋值给上一个结点的 next 指针，这样该元素就无法被访问到，最终会被垃圾回收♻️自动回收了

例如，删除链表结点中可以被 5 整除的结点

/**
 * @description: 删除可以被 n 整除的元素
 * @param {ListNode} head 头结点
 * @param {number} n 除数
 * @return {void}
 */
function deleteNodeByEntire(head, n) {
  let cur = new ListNode()
  cur.next = head

  while (cur.next) {
    if (cur.next.val % n === 0) {
      cur.next = cur.next.next
    }
    cur = cur.next
  }
}

deleteNodeByEntire(node1, 5)
console.log(linkedListToString(node1))
// val: 1|next =>val: 3|next =>val: 11|next =>val: 23|next =>null

在进行删除类的操作时需要添加一个前置元素，不然第一个元素会操作不到

修改结点

修改结点可以看做是是删除操作+添加操作

将数值为 5 的元素替换为 7

/**
 * @description: 替换值为 n 的结点
 * @param {ListNode} oldList 原链表
 * @param {number} n 目标数值
 * @param {ListNode} newNode 新结点
 * @return {void}
 */
function replaceNodeByValue(oldList, n, newNode) {
  let cur = new ListNode()
  cur.next = oldList

  while (cur.next) {
    if (cur.next.val === n) {
      newNode.next = cur.next.next
      cur.next = newNode
      break
    }
    cur = cur.next
  }
}

const newNode = new ListNode(7)
replaceNodeByValue(node1, 5, newNode)
console.log(linkedListToString(node1));
// val: 1|next =>val: 3|next =>val: 7|next =>val: 11|next =>val: 23|next =>null

链表进阶操作

快慢指针

使用两个指针操作链表，常见的操作有删除链表中倒数第 n 个结点

删除的过程如下

创建两个指针同时指向 head
将 fast 指针向后移动 n 个结点，此时 fast 和 slow 之间的差值是 n
同时向后移动 fast 和 slow，二者之间的距离始终保持 n，直到 fast 移动到最后一个结点
删除 slow.next 结点，因为slow 和 fast 之间的差值为 n，所以倒数第 n 个元素是 slow 的下一个元素

代码实现如下：

/**
 * @description: 删除倒数第 n 个结点
 * @param {ListNode} list 链表
 * @param {number} n 倒数第 n 个
 * @return {void}
 */
function deleteLastNnd(list, n) {
  let head = new ListNode()
  head.next = list
  let fast = head
  let slow = head

  while (n !== 0) {
    fast = fast.next
    n--
  }

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

  slow.next = slow.next.next
}

deleteLastNnd(node1, 3)
console.log(linkedListToString(node1));
// val: 1|next =>val: 3|next =>val: 11|next =>val: 23|next =>null

多指针

多指针的情况最常出现在反转链表中，例如，将指定链表进行反转

过程如下

创建三个指针，分辨指向三个元素（pre 开始指向null，因为链表的最后是 null）
将 cur.next 指向 pre，此时 pre 和 cur 已经反转
将 pre指向当前的 cur，作为下一次循环的 pre，将cur指向 next 作为下一次循环的 cur

只需要不停地循环直到最后一个节点，就可以将整个链表反转

代码实现如下：

/**
 * @description: 反转链表
 * @param {ListNode} list 要反转的链表
 * @return {ListNode} 反转后的链表
 */
function reverse(list) {
  let pre = null
  let cur = list

  while (cur) {
    let next = cur.next
    cur.next = pre
    pre = cur
    cur = next
  }

  return pre
}

console.log(linkedListToString(reverse(node1)));
// val: 23|next =>val: 11|next =>val: 5|next =>val: 3|next =>val: 1|next =>null

进阶：反转部分链表

将链表中 m-n 部分的链表进行反转（0<m,n<list.length）

过程如下

遍历至第 m-1 结点，将当前节点标记为 ledftHead 用于拼接反转列表，然后将后面的结点依次标记为 pre（同时标记为 start，用于拼接n 结点之后的链表）、 cur、next
开始反转，循环到 n 结点
将 leftHead 的 next 指向 pre，start 的 next 指向 cur

代码实现如下：

/**
 * @description: 反转部分链表
 * @param {ListNode} list 要操作的链表
 * @param {number} m 开始位置
 * @param {number} n 结束位置
 * @return {ListNode} 反转后的链表
 */
function partReverse(list, m, n) {
  let head = new ListNode()
  head.next = list

  let p = head
  let pre, cur, start, leftHead
  for (let i = 0; i < m - 1; i++) {
    p = p.next
  }
  leftHead = p
  start = leftHead.next
  pre = start
  cur = pre.next

  for (let i = m; i < n; i++) {
    let next = cur.next
    cur.next = pre
    pre = cur
    cur = next
  }

  leftHead.next = pre
  start.next = cur

  return head.next
}

console.log(linkedListToString(partReverse(node1, 2, 4)));
// val: 1|next =>val: 11|next =>val: 5|next =>val: 3|next =>val: 23|next =>null

环形链表

环形链表是一种特殊的链表，将最后一个节点与之前的节点连接起来，永远不会遍历到最后一个节点

判断一个链表是否为环形链表的代码如下：

/**
 * @description: 判断是否为环形链表
 * @param {ListNode} list 链表
 * @return {boolean} 是否是环形链表
 */
function isCircleLinkedList(list) {
  let cur = list
  while (cur) {
    if (cur.flag) {
      return true
    } else {
      cur.flag = true
      cur = cur.next
    }
  }

  return false
}

// console.log(isCircleLinkedList(node1)); // false
node5.next = node1
console.log(isCircleLinkedList(node1)); // true
// 不能同时执行两次，第一次会全打上 flag 标记

进阶一点的题目会让你找出环形链表的起点

只要掌握了环形链表的特性，这类题目的方法都是相同的，判断为环形链表的节点便是环形链表的起点

/**
 * @description: 寻找环形链表的起点
 * @param {ListNode} list 要搜索的链表
 * @return {ListNode | null} 环形链表起点或者 null
 */
function searchCircleStart(list) {
  let cur = list
  while (cur) {
    if (cur.flag) {
      return cur
    } else {
      cur.flag = true
      cur = cur.next
    }
  }

  return null
}

// console.log(searchCircleStart(node1)); // null
node5.next = node2
console.log(searchCircleStart(node2).val); // 3

还可以使用快慢指针来判断是否存在环形链表

设置两个指针 fast 和 slow，fast 步长为 2，slow 步长为 1，则移动 n 次之后，fast 走过的路程为 2n，slow 走过的路程为 n，两个指针的差值为 n，如果此时二者相遇，说明环形链表的长度为 n，如果 fast 的 next 为 null 则不存在环形链表。

统计链表中的环形链表长度，不存在环形链表返回 0

/**
 * @description: 统计链表中环形链表的长度
 * @param {ListNode} list 要操作的链表
 * @return {number} 环形链表长度
 */
function countCircleLength(list) {
  let head = new ListNode()
  head.next = list

  let slow = head,
    fast = head

  let count = 0
  while (slow && fast) {
    if (slow === fast && slow.val) {
      return count
    } else {
      count++
      slow = slow.next
      fast = fast.next.next
    }
  }

  return count
}

node5.next = node2
console.log(countCircleLength(node1)); // 4

链表

基础链表操作

查找结点

增加结点

删除结点

修改结点

链表进阶操作

快慢指针

多指针

环形链表

前后端非对称加密

线段树

小枫